from efi logs ber without can cto field
Input
Output
Sample Input
- 7 2
- 2
- 1
- 1
- 2
- 2
- 1
- 1
Sample Output
- 6
Hint
设计状态 dp[i][j] 代表到 I 时间转换了 j 次的最大收益,那么状态显然可以由之前的状态转还是不转转移过来,注意加上一段区间的值可以用前缀和来优化。
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<iostream>
- #include<cmath>
- #include<algorithm>
- #include<vector>
- #include<stack>
- #include<queue>
- #include<map>
- #define RG register
- #define IL inline
- #define pi acos(-1.0)
- #define ll long long
- using namespace std;
- int tree1[1005],tree2[1005];
- int dp[1005][35];
- int T,W;
- int main() {
- scanf("%d%d",&T,&W);
- for(int i=1;i<=T;i++){
- int type;
- scanf("%d",&type);
- if(type==1) tree1[i]=1;
- else tree2[i]=1;
- tree1[i]+=tree1[i-1];
- tree2[i]+=tree2[i-1];
- }
- for(int i=1;i<=T;i++)
- for(int j=0;j<i;j++){
- for(int w=0;w<=W;w++){
- if(w%2==0){
- dp[i][w]=max(dp[i][w],dp[j][w]+tree1[i]-tree1[j]);
- if(w+1<=W) dp[i][w+1]=max(dp[i][w+1],dp[j][w]+tree2[i]-tree2[j]);
- } else{
- dp[i][w]=max(dp[i][w],dp[j][w]+tree2[i]-tree2[j]);
- if(w+1<=W) dp[i][w+1]=max(dp[i][w+1],dp[j][w]+tree1[i]-tree1[j]);
- }
- }
- }
- int maxn=0;
- for(int i=0;i<=W;i++) maxn=max(maxn,dp[T][i]);
- cout<<maxn;
- return 0;
- }
POJ 2385 Apple Catching
来源: http://www.bubuko.com/infodetail-2280265.html