還是SGU的數(shù)據(jù)強(qiáng)啊，同樣一道題目，我的代碼明顯存在Bug的，對全負(fù)數(shù)的情況處理不周，看來以后不能以AC為目標(biāo)。
代碼的健壯性是值得商榷的。
#include <stdio.h>
#include <string.h>
#define N 105
#define INF 1 << 28
int a[N][N], pre[N][N], stack[N];
int main()
{
int f, v;
while(~scanf("%d %d", &f, &v))
{
for(int i = 1; i <= f; i++)
for(int j = 1; j <= v; j++)
{
scanf("%d", &a[i][j]);
if(i > j) a[i][j] = -INF;//這里不加，可以過PKU，不加這句后面的循環(huán)需要改動其實位置，不然是錯誤的。
pre[i][j] = -1;
}
for(int i = 2; i <= f; i++)
{
for(int j = i; j <= v; j++)
{
int mmin = -INF;
for(int k = 1; k < j; k++)
{
if(a[i - 1][k] > mmin)
{
mmin = a[i - 1][k];
pre[i][j] = k;
}
}
a[i][j] += mmin;
}
}
int ans = -INF, top = 0;
for(int i = f; i <= v; i++)
{
if(a[f][i] > ans)
{
ans = a[f][i];
stack[top] = i;
}
}
while(f != 1)
{
int t = stack[top];
stack[++top] = pre[f][t];
f--;
}
printf("%d\n", ans);
for(int i = top; i >= 0; i--)
{
printf("%d", stack[i]);
if(i) printf(" ");
else printf("\n");
}
}
return 0;
}