每个花按序号顺序放到窗口,不同窗口可有不同观赏值,所有花都要放上去,求最大观赏值和花的位置。
dp,dp[i][j]表示前i朵花最后一朵在j位置的最大总观赏值。
dp[i][j]=max(dp[i-1][k]+f[i][j])
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=105;
int n,w,ans=-99999;
int dp[N][N],f[N][N],last[N][N],ansp[N];
int main()
{
scanf("%d%d",&n,&w);
for(int i=1; i<=n; i++)
{
for(int j=1; j<=w; j++)
{
scanf("%d",&f[i][j]);
}
}
for(int i=1; i<=n; i++)
{
for(int j=i; j<=w-n+i; j++)
{
dp[i][j]=dp[i-1][i-1]+f[i][i];
for(int k=i-1; k<j; k++)
{
if(dp[i-1][k]+f[i][j]>dp[i][j])
{
dp[i][j]=dp[i-1][k]+f[i][j];
last[i][j]=k;
}
}
if(i==n && dp[n][j]>ans)
{
ans=dp[n][j];
ansp[n]=j;
}
}
}
int k=ansp[n];
for(int i=n; i>0; i--)
{
k=last[i][k];
ansp[i-1]=k;
}
printf("%d\n",ans);
for(int i=1; i<=n; i++)
printf("%d ",ansp[i]);
return 0;
}