HDU 1024 Max Sum Plus Plus
// dp[i][j] = max(dp[i][j-1], dp[i-1][t]) + num[j] // pre[j-1] 存放dp[i-1][t] 里的 (1<=t<=j-1)最大值。 //dp[j] = max(dp[j-1], pre[j-1]) + num[j]; #include <stdio.h> #include <string.h> #include <iostream> #define inf 100000000 #define maxn 1000010 using namespace std; int pre[maxn]; int num[maxn]; int dp[maxn]; int main() { //freopen("in.cpp", "r", stdin); int m, n; while(~scanf("%d%d", &m, &n)) { for (int i=1; i<=n; ++i) scanf("%d", &num[i]); pre[0] = 0; dp[0] = 0; memset(pre, 0, sizeof(pre)); int maxx = -inf; for (int i=1; i<=m; ++i) { maxx = -inf; for (int j=i; j<=n; ++j) { dp[j] = max(dp[j-1], pre[j-1]) + num[j]; //pre[j-1] = max(dp[j-1], pre[j-2]); pre[j-1] = maxx; maxx = max(maxx, dp[j]); } } printf("%d ", maxx); } return 0; }
POJ 1322 Chocolate
二维:
#include <stdio.h> #include <iostream> #include <string.h> using namespace std; double dp[10010][210]; bool judge(int n, int m, int k) { if (m > n || m > k) return false; if ((m+n)%2) return false; return true; } int main() { int k, n, m; // freopen("in.cpp", "r", stdin); while (~scanf("%d", &k) && k) { scanf("%d%d", &n, &m); if (judge(n, m, k) == false) { printf("0.000 "); continue; } if (n>10000) { if (n%2) n = 10003; else n = 10004; } memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i=1; i<=n; ++i) { for (int j=0; j<=i && j<=k; ++j) { if ((i+j)%2) continue; if(j>0) dp[i][j] += dp[i-1][j-1]*(1-(j-1)*1.0/k); if(j<k) dp[i][j] += dp[i-1][j+1]*(1.0*(j+1)/k); } } printf("%.3f ", dp[n][m]); } return 0; }
一维:
#include <stdio.h> #include <iostream> #include <string.h> using namespace std; double dp[1000010]; double pre[1000010]; bool judge(int n, int m, int k) { if (m > n || m > k) return false; if ((m+n)%2) return false; return true; } int main() { int k, n, m; //freopen("in.cpp", "r", stdin); while (~scanf("%d", &k) && k) { scanf("%d%d", &n, &m); if (judge(n, m, k) == false) { printf("0.000 "); continue; } if (n>10000) { if (n%2) n = 10003; else n = 10004; } memset(dp, 0, sizeof(dp)); memset(pre, 0, sizeof(pre)); pre[0] = 1; for (int i=1; i<=n; ++i) { //memset(dp, 0, sizeof(dp)); for (int j=0; j<=i && j<=k; ++j) { dp[j] = 0; if ((i+j)%2) continue; if(j>0) dp[j] += pre[j-1]*(1-(j-1)*1.0/k); if(j<k) dp[j] += pre[j+1]*(1.0*(j+1)/k); } for (int j=0; j<=i && j<=k; ++j) { pre[j] = dp[j]; } } printf("%.3f ", pre[m]); } return 0; }