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