首页 > 代码库 > Poetize6: Acting Cute
Poetize6: Acting Cute
3042: Acting Cute
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 59 Solved: 36
[Submit][Status]
Description
正在rainbow的城堡游玩的freda恰好看见了在地毯上跳舞卖萌的水叮当……于是……
freda:“呜咕>_< 我也要卖萌T_T!”
rainbow给了freda N秒的自由活动时间,不过由于刚刚游览城堡有些累了,freda只想花B秒的时间来卖萌,剩下的时间她要在rainbow的城堡里睡个好觉好好休息一下。
rainbow给这N秒每秒定义了一个值Ui,如果第i秒钟freda在卖萌,那么她可以获得Ui点卖萌指数lala~
freda开始卖萌后可以随时停止,休息一会儿之后再开始。不过每次freda开始卖萌时,都需要1秒来准备= =,这一秒是不能获得卖萌指数的。当然,freda卖萌和准备的总时间不能超过B。
更特殊的是,这N秒钟时间是环形的。也就是freda可以从任意时间开始她的自由活动并持续N秒。
为了使自己表现得比水叮当更萌,现在freda想知道,她最多能获得多少卖萌指数呢?
Input
第一行包含两个整数N和B。
第2~N+1行每行一个整数,其中第i+1行的整数表示Ui。
Output
输出一个整数,表示freda可以获得的最大卖萌指数。
Sample Input
5 3
2
0
3
1
4
2
0
3
1
4
Sample Output
6
对于100%的数据,0<=B<=N<=3600,0<=Ui<=200000。
样例解释:
freda选择从第2秒开始她的自由活动,持续N秒(2、3、4、5、1)。第4秒开始准备,第5、1秒卖萌(时间是环形的),获得2+4=6点卖萌指数。
对于100%的数据,0<=B<=N<=3600,0<=Ui<=200000。
样例解释:
freda选择从第2秒开始她的自由活动,持续N秒(2、3、4、5、1)。第4秒开始准备,第5、1秒卖萌(时间是环形的),获得2+4=6点卖萌指数。
HINT
Source
Poetize6
题解:
我连n^3的DP都没想出,给跪了!
看了题解很好想。。。
f[i][j][k]表示走到i,卖萌了j次,当前状态是k,k=0表没有卖萌,k=1表处于卖萌状态。
然后
f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1])
f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j-1][1]+a[i])
然后如果是环形的话
我们可以证明如果最优解不是从1出发的,那么n和1的肯定都在卖萌!
否则 我们就可以从1开始DP从而得出这个最优值!
应该很好理解的。
然后我们强制把n和1都设定为处在卖萌状态了,然后再做一次DP
出题人的题解:http://hi.baidu.com/lydrainbowcat/item/0691bf7f2c46503c70442338
不滚动也能A,我作死写了滚动结果t放在循环里了。。。查了0.5h。。。sad
具体实现如下:
代码:
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 500014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 int n,m,t,ans,a[maxn],f[2][maxn][2];32 void dp()33 {34 t=0;35 for2(i,2,n)36 {37 t=1-t;38 for0(j,m)39 {40 f[t][j][0]=max(f[1-t][j][0],f[1-t][j][1]);41 if(j)f[t][j][1]=max(f[1-t][j-1][0],f[1-t][j-1][1]+a[i]);42 } 43 }44 }45 int main()46 {47 freopen("input.txt","r",stdin);48 freopen("output.txt","w",stdout);49 n=read();m=read();50 for1(i,n)a[i]=read();51 if(m<=1)printf("0\n");52 for0(i,1)for0(j,m)for0(k,1)f[i][j][k]=-inf;53 f[0][0][0]=f[0][1][1]=0;54 dp();ans=max(f[t][m][0],f[t][m][1]);55 for0(i,1)for0(j,m)for0(k,1)f[i][j][k]=-inf;56 f[0][1][0]=f[0][1][1]=a[1];57 dp();ans=max(ans,f[t][m][1]);58 printf("%d\n",ans);59 return 0;60 }
Poetize6: Acting Cute
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。