的价值，求最大价值。
几乎是刚刚开始接触动态规划题，开始我这样想 每个东西一件一件放，dp[k]表放k物品时候已经到达最大值
dp[k]=dp[k-1]+max(放k物品所得到最大值)，这样想想不行，如果现在放最大值未必最大啊。
百度一下，发现别人用二维数组，我马上想想得二维的，于是dp[i][j]第i次放置放j容器时，所得最大值。
这样：dp[i][j]=max(dp[i-1][k])(k<=j-1;k>=i-1);画了个图，第i次选择j就是前一次中所有可能情况最大值，
这样地推，必然得到最大。最后在更新时候记录路经即可。
PS:不会dp的acmer能叫acmer吗！需要更多的dp来鞭挞我啊！渴望！
#include<iostream> //1A ，31ms
#include<cstdio>
using namespace std;
int nowmax[110][110];
int a[110][110];
int n,m;
void readin()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
for(int i=1;i<=m;i++)
nowmax[1][i]=a[1][i];
}
int fa[105][105];
int way[105];int num=0;
int main()
{
readin();
for(int i=2;i<=n;i++)
for(int j=i;j<=m-(n-i);j++) //对每个i,j
{
int maxid=1;
int max=nowmax[i-1][i-1];
for(int k=j-1;k>i-1;k--) //更新找最大的
{
if(nowmax[i-1][k]>max)
{
max=nowmax[i-1][k];
maxid=k;
}
}
nowmax[i][j]=a[i][j]+max;
fa[i][j]=maxid;
}
int ans=nowmax[n][m];
int anslast=m;
for(int k=n;k<m;k++)
{
if(ans<nowmax[n][k])
{
ans=nowmax[n][k];
anslast=k;
}
}
cout<<ans<<endl;
int maxid=anslast;
way[num++]=anslast;
for(int i=n;i>1;i--)
{
way[num++]=fa[i][maxid];
maxid=fa[i][maxid];
}
for(int i=num-1;i>=0;i--)
{
if(i!=0)printf("%d ",way[i]);
else printf("%d
",way[i]);
}
}