Sgu/104

简单动规

#include <iostream>
#include <cstring>
 
using namespace std ;
 
int Val[101][101] ;	
int DP[101][101] ;
int Res[101][101][2] ;
int F, V ;
 
void Print(int a, int b)
{
	if(a == 0 && b == 0)
		return ;
	Print(Res[a][b][0], Res[a][b][1]);
	if(Res[a][b][0] == a- 1)
		cout << b << " " ;
	return ;
}
 
int main()
{
	cin >> F >> V ;
	for(int i= 1; i<= F; i++)
	{
		for(int j= 1; j<= V; j++)
			cin >> Val[i][j];
		DP[i][i]= DP[i- 1][i- 1]+ Val[i][i];
	}
 
	for(int i= 1; i<= F; i++)
		for(int j= i+ 1; j<= V; j++)
		{
 
				DP[i][j]= DP[i][j- 1] ;
				Res[i][j][0]= i;
				Res[i][j][1]= j- 1;
			if(DP[i- 1][j- 1]+ Val[i][j] > DP[i][j])
			{
				DP[i][j]= DP[i- 1][j- 1]+ Val[i][j];
				Res[i][j][0]= i- 1;
				Res[i][j][1]= j- 1;
			}
		}
 
	cout << DP[F][V] << endl ;
	Print(F, V);
	cout << endl ;
	//system("pause");
	return 0 ;
}

//by hza
#include<stdio.h>
 
const int INF=1000000000;
const int MAX=100+10;
int love[MAX][MAX];
int f[MAX][MAX];
int last[MAX][MAX];
int F,V;
 
int main()
{
	freopen("104.in","r",stdin);
	freopen("104.out","w",stdout);
	int i,j,k;
	scanf("%d%d",&F,&V);
	for(i=1;i<=F;++i)
		for(j=1;j<=V;++j)
			scanf("%d",&love[i][j]);
	for(i=1;i<=F;++i)
		for(j=1;j<=V;++j)
			f[i][j]=-INF;
	f[0][0]=0;
	for(i=1;i<=F;++i)
		for(j=i;j<=V;++j)
			for(k=i-1;k<j;++k)
				if(f[i-1][k]!=-INF)
					if(f[i-1][k]+love[i][j]>f[i][j])
						f[i][j]=f[i-1][k]+love[i][j],last[i][j]=k;
 
	int answer=-INF,ans[MAX],end;
	for(i=1;i<=V;++i)
		if(f[F][i]>answer)answer=f[F][i],end=i;
 
	for(i=F;i>=1;--i)
		ans[i]=end,end=last[i][end];
 
	printf("%d\n",answer);
	for(i=1;i<=F;++i)
		printf("%d ",ans[i]);
	printf("\n");
}

====================================================================

O(F*V^2)

//by a710128
#include<iostream>
#include<cstring>
using namespace std;
int f[101][101],fa[101][101],F,V,map[101][101],out[101];
int main()
{
	cin>>F>>V;
	for(int i=1;i<=F;i++)
		for(int j=1;j<=V;j++) cin>>map[i][j];
	memset(f,0x80,sizeof(f));f[0][0]=0;
	for(int i=1;i<=F;i++)
		for(int j=1;j<=V;j++)
			for(int k=i-1;k<j;k++)
				if(f[i-1][k]+map[i][j]>f[i][j])
				{
					f[i][j]=f[i-1][k]+map[i][j];
					fa[i][j]=k;
				}
	int ans=1;
	for(int i=2;i<=V;i++) if(f[F][i]>f[F][ans]) ans=i;
	cout<<f[F][ans]<<endl;
	for(int i=F;i>=1;ans=fa[i][ans],i--) out[i]=ans;
	for(int i=1;i<=F;i++) cout<<out[i]<<" ";
	return 0;
}