很水，我卻做了很久，唉，細節的東西沒處理好。。。
又要順序又要最大的，看上去感覺就和LCS一樣，很容易想出狀態轉移公式：dp[i,j] = max{dp[i - 1][j - 1] + a[i][j], dp[i - 1][j]}.
AC代碼如下：
[cpp]
#include <cstdio>
const int maxn = 100 + 10;
const int min = -1000000;
int a[maxn][maxn] = {0};
int dp[maxn][maxn];
bool path[maxn][maxn] = {0};
void pt(int i, int j){ //find path
if (i == 0)
return;
if (path[i][j] == 1)
{
pt(i - 1, j - 1);
printf("%d ", j);
}
else
pt(i, j - 1);
return;
}
int main()
{
int f, v;
int i, j;
scanf("%d%d", &f, &v);
for (i = 1; i <= f; i++)
for (j = 1; j <= v; j++)
scanf("%d", &a[i][j]);
for (i = 1; i <= f; i++)
for (j = 0; j <= v; j++)
dp[i][j] = min; //ini
for (i = 1; i <= f; i++)
for (j = i; j <= v && i <= i + f; j++)
if (dp[i - 1][j - 1] + a[i][j] <= dp[i][j - 1])
dp[i][j] = dp[i][j - 1];
else
dp[i][j] = dp[i - 1][j - 1] + a[i][j], path[i][j] = 1;
printf("%d\n", dp[f][v]);
pt(f, v);
return 0;
}
#include <cstdio>
const int maxn = 100 + 10;
const int min = -1000000;
int a[maxn][maxn] = {0};
int dp[maxn][maxn];
bool path[maxn][maxn] = {0};
void pt(int i, int j){ //find path
if (i == 0)
return;
if (path[i][j] == 1)
{
pt(i - 1, j - 1);
printf("%d ", j);
}
else
pt(i, j - 1);
return;
}
int main()
{
int f, v;
int i, j;
scanf("%d%d", &f, &v);
for (i = 1; i <= f; i++)
for (j = 1; j <= v; j++)
scanf("%d", &a[i][j]);
for (i = 1; i <= f; i++)
for (j = 0; j <= v; j++)
dp[i][j] = min; //ini
for (i = 1; i <= f; i++)
for (j = i; j <= v && i <= i + f; j++)
if (dp[i - 1][j - 1] + a[i][j] <= dp[i][j - 1])
dp[i][j] = dp[i][j - 1];
else
dp[i][j] = dp[i - 1][j - 1] + a[i][j], path[i][j] = 1;
printf("%d\n", dp[f][v]);
pt(f, v);
return 0;
}
恩。。。復雜度o(n^2)，還好，因為數據小，尋址用遞歸做。
wa了幾次，由於如下原因：
1.沒有把dp初始化成極小，導致前面的花瓶沒有被插到花
2.本來想僅初始化必要的數值，減小不必要的開銷，但老是被一點卡住。
3.題目說輸出任何一種方案即可，但是我設定如果dp比較相等時取它對角的前一個，就被一個點卡住了。很坑啊。。。
額，以後做題要細心了。。
