題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5280

解題思路：動態(tài)規(guī)劃，dp[i][0]表示以第i個數(shù)結(jié)尾時，沒把p添加到數(shù)列中，dp[i][1]表示以第i個數(shù)結(jié)尾時，已經(jīng)把p添加入數(shù)列中。

#include<iostream> #include<cstdio> #include<cstring> #define max(a,b) a > b ? a : b using namespace std;typedef long long LL; const int maxn = 1005; const LL inf = 0x3f3f3f3f*0x3f3f3f3f; int n; LL p,A[maxn],dp[maxn][2];int main() {int t;scanf("%d",&t);while(t--){scanf("%d%lld",&n,&p);for(int i = 1; i <= n; i++)scanf("%lld",&A[i]);dp[1][0] = A[1]; dp[1][1] = p;LL ans = -inf;for(int i = 2; i <= n; i++){dp[i][0] = max(dp[i-1][0] + A[i],A[i]);dp[i][1] = max(A[i],p); //之前一直WA的原因。。太粗心了。。dp[i][1] = max(dp[i][1],dp[i-1][1] + A[i]);dp[i][1] = max(dp[i][1],dp[i-1][0] + p);}for(int i = 1; i <= n; i++)ans = max(ans,dp[i][1]);printf("%lld\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 5280(最大子串和变形，dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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