POJ 1163 数字三角形

DP经典题，IOI94考题，在各大OJ上都有

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<set>
 4 #include<cstdio>
 5 #include<cstdlib>
 6 #include<cmath>
 7 using namespace std;
 8 #define FOR(i,j,k) for(int i=j;i<=k;i++)
 9 #define FORD(i,j,k) for(int i=j;i>=k;i--)
10 #define LL long long
11 #define maxn 1010
12 int cost[maxn][maxn],dp[maxn][maxn];
13 int T,n;
14 int main()
15 {
16     cin>>n;
17     FOR(i,1,n)
18         FOR(j,1,i)
19             cin>>cost[i][j];
20     FORD(i,n,1)
21         FOR(j,1,i)
22             dp[i][j]=cost[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
23     cout<<dp[1][1]<<endl;
24 return 0;
25 }

水水的写法

这道题还有加强的版本，增加了数据规模和数据组数，然并卵如UESTC 1011

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<set>
 4 #include<cstdio>
 5 #include<cstdlib>
 6 #include<cmath>
 7 using namespace std;
 8 #define FOR(i,j,k) for(int i=j;i<=k;i++)
 9 #define FORD(i,j,k) for(int i=j;i>=k;i--)
10 #define LL long long
11 #define maxn 110
12 int cost[maxn][maxn],dp[maxn][maxn];
13 int T,n;
14 int main()
15 {
16 cin>>T;
17 FOR(i,1,T)
18 {
19     cin>>n;
20     FOR(i,1,n)
21         FOR(j,1,i)
22             cin>>cost[i][j];
23     FORD(i,n,1)
24         FOR(j,1,i)
25             dp[i][j]=cost[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
26     cout<<dp[1][1]<<endl;
27     FOR(i,1,n)
28     FOR(j,1,n)
29     {cost[i][j]=0;dp[i][j]=0;}
30 }
31 return 0;
32 }

依然水水的写法

据我理解：dp是建立在各子问题的独立与子问题的最优子结构上的

值得注意的是，这道题的dp有两种写法

dp[i][j]既可以表示以(i,j)为起点的路径长度最大值【1】

也可以表示以(i,j)为终点的路径长度最大值【2】

当然都是最大值啦DAZE

如果这题要输出任意一种最长路径的话,用【1】进行DP较优

这是因为路径的直接无回溯输出是由顶向底，所以它要求每个经过点都有确定的后驱，所以用【1】

当然用【2】的话写个简单的回溯取解就好了，有点烦啊。。。

话说这道题的dp决策树似乎是个DAG，说来DAG满足各种dp条件啊，那岂不是只要碰到DAG就可以拿dp乱搞了？ふっふっと