Problem Address：http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1507
Problem Address：http://poj.org/problem?id=3176
这两道题，第二道是简单的DP，第一道就有点难。
最近在学DP，想好好搞清楚。
今天算是有点明白了。
不过第一道却不是自己做出来的，而是看了某牛的代码写出来的。
不过也正是因为这一道题而逐渐弄懂了DP。
但是效率似乎并不是最好的，有待优化。
刚才写了第二道，算是自己写的第一道DP吧。
提交上去后，打出了“Waiting”，刷新，还是“Waiting”，再刷，还是。自己有点担心是不是超时了。
然后看到下面那个还打着“Running & Judging”，放了一下心。
再刷，打出了“WA”。我想怎么可能呢？
向左看去，发现用户名不对。往下找，终于看到蓝色的AC~
就这样过了~
好惊险！
以下贴代码：
ZJUT1507代码如下：
#include <iostream>using namespace std;int n,num[1001],dp[2005][2005];int search(int L, int R, int i){ if (dp[L][R]!=-1) return dp[L][R]; int a = search(L+1,R,i+1)+num[L]*i; int b = search(L,R-1,i+1)+num[R]*i; dp[L][R] = a>b?a:b; return dp[L][R];}int main(){ int i,j,total; while(scanf("%d", &n)!=EOF) { for (i=1; i<=n; i++) { for (j=1; j<=n; j++) { dp[i][j] = -1; } } for (i=1; i<=n; i++) { scanf("%d", &num[i]); dp[i][i]=n*num[i]; } total = search(1,n,1); printf("%d/n", total); } return 0;}
POJ3176代码如下：
#include <iostream>using namespace std;int a[355][355];int main(){ int i,j,n; while(scanf("%d", &n)!=EOF) { for (i=0; i<n; i++) { for (j=0; j<=i; j++) { scanf("%d", &a[i][j]); } } for (i=n-2; i>=0; i--) { for (j=0; j<=i; j++) { if (a[i+1][j]>a[i+1][j+1]) a[i][j] += a[i+1][j]; else a[i][j] += a[i+1][j+1]; } } printf("%d/n", a[0][0]); } return 0;}
热烈庆祝逐渐弄懂DP~~
