div1 250pt:

　　题意:100*100的01矩阵，找出来面积最大的“类似国际象棋棋盘”的子矩阵。

　　解法：枚举矩阵宽(水平方向)的起点和终点，然后利用尺取法来找到每个固定宽度下的最大矩阵，不断更新答案。

 // BEGIN CUT HERE

 // END CUT HERE

 #line 5 "TheMatrix.cpp"

 #include<cstdio>

 #include<sstream>

 #include<cstring>

 #include<cstdlib>

 #include<ctime>

 #include<cmath>

 #include<cassert>

 #include<iostream>

 #include<string>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<stack>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pii;

 class TheMatrix

 {

     public:

     bool check(vector<string>& s,int start,int end,int row){

         for(int i = start + ;i <=end;i++)

             if(s[row][i]==s[row][i-])return false;

         return true;

     }

     bool ok(vector<string>& s,int start,int end,int row){

         for(int i=start;i<=end;i++)

             if(s[row][i]==s[row-][i])return false;

         return true;

     }

     int MaxArea(vector <string> s){

     //$CARETPOSITION$

         int answer = ;

         int n=s.size(),m=s[].size();

         for(int i=;i<m;i++)

             for(int j=;j<m;j++){

                 int down=,up=;

                 for(down=;down<n;down++){

                     if(check(s,i,j,down)){

                         up=down+;

                         while(up<n&&ok(s,i,j,up))up++;

                         int area=(j-i+)*(up-down);

                         answer=max(answer,area);

                         down=up-;

                     }

                 }

             }

         return answer;

     }

 // BEGIN CUT HERE

     public:

     void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); if ((Case == -) || (Case == )) test_case_4(); if ((Case == -) || (Case == )) test_case_5(); if ((Case == -) || (Case == )) test_case_6(); if ((Case == -) || (Case == )) test_case_7(); }

     private:

     template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }

     void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }

     void test_case_0() { string Arr0[] = {"",

  ""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, MaxArea(Arg0)); }

     void test_case_1() { string Arr0[] = {""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, MaxArea(Arg0)); }

     void test_case_2() { string Arr0[] = {""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, MaxArea(Arg0)); }

     void test_case_3() { string Arr0[] = {"",

  "",

  ""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, MaxArea(Arg0)); }

     void test_case_4() { string Arr0[] = {""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, MaxArea(Arg0)); }

     void test_case_5() { string Arr0[] = {"",

  ""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, MaxArea(Arg0)); }

     void test_case_6() { string Arr0[] = {"",

  "",

  "",

  ""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, MaxArea(Arg0)); }

     void test_case_7() { string Arr0[] = {"",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  "",

  ""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, MaxArea(Arg0)); }

 // END CUT HERE

 };

 // BEGIN CUT HERE

 int main(){

     TheMatrix ___test;

     ___test.run_test(-);

     return ;

 }

 // END CUT HERE

250pt

div1 500pt:

　　题意：有个人有个飞机，起初有F升油，有很多个任务，第i个任务消耗duration[i]油，完成之后得到refuel[i]升油，求最多能完成的任务数。

　　解法：先按照refuel降序排列，然后背包。

　　　　why?

　　　　对于两个任务，refuel大的在前面做一定要优于在后面做。假设现在剩余F升油，有两个任务a,b,其中duration[a] > duration[b],如果a先做，那么做完之后会剩余F - duration[a] + refuel[a]升油，如果b先做，会剩余F - duration[b] + refuel[b]升油，也就是说，如果两个都能做完的话，至少要保证F-duration[a]-duraion[b]+refuel[a/b]>=0,

显然先做refuel大的更可能完成。

　　

 // BEGIN CUT HERE

 // END CUT HERE

 #line 5 "AlbertoTheAviator.cpp"

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<ctime>

 #include<cmath>

 #include<sstream>

 #include<cassert>

 #include<iostream>

 #include<string>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<stack>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pii;

 int dp[][];

 pii hs[];

 bool cmp(pii a,pii b){

     return a.first > b.first;

 }

 class AlbertoTheAviator

 {

     public:

     int MaximumFlights(int F, vector <int> duration, vector <int> refuel){

     //$CARETPOSITION$

         int n = duration.size();

         for(int i = ;i < n;i++){

             hs[i].first = refuel[i];

             hs[i].second = duration[i];

         }

         sort(hs,hs+n,cmp);

         memset(dp,-,sizeof(dp));

         dp[][F] = ;

         for(int i = ;i < n;i++){

             for(int j=;j<=;j++)dp[i+][j]=dp[i][j];

             for(int j=hs[i].second;j <= ;j++){

                 if(dp[i][j] == -)continue;

                 dp[i+][j-hs[i].second+hs[i].first]=max(dp[i+][j-hs[i].second+hs[i].first],dp[i][j]+);

             }

         }

         int answer = ;

         for(int i = ;i <= ;i++)

             answer = max(answer,dp[n][i]);

         return answer;

     }

 // BEGIN CUT HERE

     public:

     void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); if ((Case == -) || (Case == )) test_case_4(); if ((Case == -) || (Case == )) test_case_5(); }

     private:

     template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }

     void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }

     void test_case_0() { int Arg0 = ; int Arr1[] = {}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arr2[] = {}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); int Arg3 = ; verify_case(, Arg3, MaximumFlights(Arg0, Arg1, Arg2)); }

     void test_case_1() { int Arg0 = ; int Arr1[] = {, }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arr2[] = {, }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); int Arg3 = ; verify_case(, Arg3, MaximumFlights(Arg0, Arg1, Arg2)); }

     void test_case_2() { int Arg0 = ; int Arr1[] = {, , , }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arr2[] = {, , , }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); int Arg3 = ; verify_case(, Arg3, MaximumFlights(Arg0, Arg1, Arg2)); }

     void test_case_3() { int Arg0 = ; int Arr1[] = {, }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arr2[] = {, }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); int Arg3 = ; verify_case(, Arg3, MaximumFlights(Arg0, Arg1, Arg2)); }

     void test_case_4() { int Arg0 = ; int Arr1[] = {}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arr2[] = {}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); int Arg3 = ; verify_case(, Arg3, MaximumFlights(Arg0, Arg1, Arg2)); }

     void test_case_5() { int Arg0 = ; int Arr1[] = {, , , , , , , , , , , , , }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); int Arr2[] = {, , , , , , , , , , , , , }; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); int Arg3 = ; verify_case(, Arg3, MaximumFlights(Arg0, Arg1, Arg2)); }

 // END CUT HERE

 };

 // BEGIN CUT HERE

 int main(){

     AlbertoTheAviator ___test;

     ___test.run_test(-);

     return ;

 }

 // END CUT HERE

500pt

　　

最新文章

  1. Command调用存储过程小实例
  2. 迷茫的it男，我该何去何从
  3. 【转】15个无比华丽的HTML5/CSS3动画应用
  4. crosswalk-webview
  5. C语言文法 改
  6. Asp.Net原理Version3.0_页面声明周期
  7. Android客户端中Bitmap的下载过程和缓存机制
  8. python之文件操作(基础）
  9. C# 泛型单例
  10. vlan 知识学习
  11. hiho一下 第207周
  12. npm 是node.js下带的一个包管理工具
  13. Android 开发 倒计时功能 转载
  14. Linux 常用命令——文件处理命令
  15. BZOJ.3757.苹果树(树上莫队)
  16. QueryRunner类实战
  17. Python3基础 dict pop 弹出指定键的项
  18. Java打印水仙花数
  19. phar 反序列化学习
  20. 【Python】定时调度

热门文章

  1. mongodb windows 开机启动
  2. 前端拖动div 效果
  3. 复制webp图片到word || 微信webp图片不能复制 || 如何复制webp到word
  4. 自定义函数导致的sql性能问题
  5. ArchLinux 安装笔记
  6. angularJS transclude
  7. 如何用纯 CSS 创作一个容器厚条纹边框特效
  8. qt 窗体间通信
  9. LeetCode（101）Symmetric Tree
  10. javax.servlet.jsp.JspTagException: Neither BindingResult nor plain target object for bean (蛋疼死我了)