題意：

水果忍者游戲，給出N個(gè)水果的出現(xiàn)時(shí)間和消失時(shí)間。

每次切可以清除該時(shí)刻中屏幕上的所有水果，只有combo>=3的時(shí)候才得分，得分為combo的值。

題解：

可以把每個(gè)水果看成是一段時(shí)間區(qū)間。

然后把這些區(qū)間按照出現(xiàn)時(shí)間為第一關(guān)鍵字，消失時(shí)間為第二關(guān)鍵字排序。

我們定義dp方程dp[i]表示最后一刀切掉第i個(gè)水果，所獲得的最大積分。

那么，最優(yōu)的方案肯定是在第i個(gè)水果出現(xiàn)時(shí)間進(jìn)行切。

這樣的話，轉(zhuǎn)移方程

dp[i] = max(dp[i],dp[j-1]+sum);

其中sum表示j到i之間所有結(jié)束時(shí)間>=第i個(gè)水果出現(xiàn)時(shí)間的水果數(shù)量。

但是注意！

這個(gè)題目有一個(gè)限制，就是說(shuō)每次切必定將所有的水果都切完。

也就時(shí)候如果j-1水果的出現(xiàn)時(shí)間=第j個(gè)水果的出現(xiàn)時(shí)間的話，那么是不能進(jìn)行轉(zhuǎn)移的，因?yàn)榍械趈-1個(gè)水果的時(shí)候必然把第j個(gè)水果切掉，不會(huì)留下。

代碼：

#include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; bool cmp(P p1,P p2){if(p1.first == p2.first) return p1.second < p2.second;return p1.first < p2.first; } const int maxn = 1005; P ps[maxn]; int dp[maxn]; int n; int main(){int T,cas=0;cin>>T;ps[0].first = ps[0].second = -1;while(T--){memset(dp,0,sizeof(dp));scanf("%d",&n);for(int i = 1;i <= n;++i){int a,b;scanf("%d %d",&a,&b);ps[i] = make_pair(a,b);} sort(ps+1,ps+1+n,cmp);int ans = 0;if(n >= 3){for(int i = 3;i <= n;++i){int tim = ps[i].first;int sm = 0;for(int j = i;j >= 1;--j){if(ps[j].second >= tim) sm++;if(ps[j-1].first != ps[j].first)dp[i] = max(dp[i],dp[j-1] + (sm >= 3?sm:0));}ans = max(ans,dp[i]);}}printf("Case #%d: %d\n",++cas,ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Juice Extractor dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。