/*
動態轉移方程：dp[i][j]=max(dp[i-1]+a[i], max(dp[t][j-1])+a[i]) (j-1<=t<i)
表示的是前i個數j個字段和的最大值是多少！
*/
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define N 10000 5 using namespace std; 6 7 int dp[N][N], num[N]; 8 9 int main() 10 { 11 int n, m, i, j, k; 12 while(scanf("%d%d", &m, &n)!=EOF) 13 { 14 for(i=1; i<=n; i++) 15 scanf("%d", &num[i]); 16 memset(dp, 0, sizeof(dp)); 17 for(j=1; j<=m; j++) 18 for(i=j; i<=n-m+j; i++) 19 if(i>j) 20 { 21 dp[i][j]=dp[i-1][j]+num[i]; 22 for(k=j-1; k<i; k++)//可以用一個Max變量一直更新 j-1 到 i-1 的 最大值 23 dp[i][j]=max(dp[i][j], dp[k][j-1]+num[i]); 24 } 25 else dp[i][j]=dp[i-1][j-1]+num[i]; 26 int sum=-1; 27 for(i=m; i<=n; i++) 28 if(dp[i][m]>sum) 29 sum=dp[i][m]; 30 printf("%d\n", sum) ; 31 } 32 return 0; 33 }
/* 時間上優化一下！ */ #include<iostream> #include<cstdio> #include<cstring> #define N 1000010 using namespace std;__int64 dp[N][2], num[N];int main() {__int64 n, m, i, j, k, pos;while(scanf("%I64d%I64d", &m, &n)!=EOF){for(i=1; i<=n; i++){scanf("%I64d", &num[i]);dp[i][0]=dp[i][1]=0;}pos=1;for(j=1; j<=m; j++){ dp[j][pos]=dp[j-1][pos^1]+num[j];__int64 Max=dp[j-1][pos^1];for(i=j+1; i<=n-m+j; i++){Max=max(Max, dp[i-1][pos^1]);//這一塊直接將 k 的 for循環去掉 dp[i][pos]=max(dp[i-1][pos], Max)+num[i];}pos^=1;}pos^=1;__int64 sum=-99999999;for(i=m; i<=n; i++)if(dp[i][pos]>sum)sum=dp[i][pos];printf("%I64d\n", sum) ;}return 0; }
1 /* 2 內存上優化一下，一維數組求解！ 3 */ 4 #include<iostream> 5 #include<cstdio> 6 #include<cstring> 7 #define N 1000010 8 using namespace std; 9 10 __int64 dp[N], num[N]; 11 12 int main() 13 { 14 __int64 n, m, i, j, k, oldN; 15 __int64 maxN;//記錄dp[k][j-1] (k>=j-1 && k<i) 只有num[i]自己屬于第 j 段 所有情況的最大值！ 16 while(scanf("%I64d%I64d", &m, &n)!=EOF) 17 { 18 for(i=1; i<=n; i++){ 19 scanf("%I64d", &num[i]); 20 dp[i]=0; 21 } 22 for(j=1; j<=m; j++) 23 { 24 maxN=max(dp[j-1], dp[j]);// Max = max(dp[j-1][pos^1], dp[j][pos^1]) 25 dp[j]=dp[j-1]+num[j]; 26 for(i=j+1; i<=n-m+j; i++) 27 { 28 oldN=dp[i];// 記錄 dp[i-1][pos^1] 29 dp[i]=max(maxN, dp[i-1])+num[i] ;// dp[j][pos] = dp[j-1][pos^1] + num[j] 30 maxN=max(oldN, maxN); 31 } 32 } 33 __int64 sum=-99999999; 34 for(i=m; i<=n; ++i) 35 if(dp[i]>sum) 36 sum=dp[i]; 37 printf("%I64d\n", sum) ; 38 } 39 return 0; 40 }
?
?
?
)
)
