3063181_ac_30ms_228k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 46 行

#include <stdio.h>

int main()
{
	int f, v;
	int i, j, k, ans;
	int dp[102][102];
	int cost[102][102];

	scanf("%d%d",&f,&v);
	for(i = 1; i <= f; i++)
	{
		for(j = 1; j <= v; j++)
		{
			scanf("%d",&cost[i][j]);
			if(i==1)
			{
				dp[i][j] = cost[i][j];
			}
			else
				dp[i][j] = -2100000000;
		}
	}
	for(i = 2; i <= f; i++)
	{
		for(j = 1; j <= v; j++)
		{
			if(i<=j)
			{
				for(k = 1; k < j; k++)
				{
					if(dp[i][j]<dp[i-1][k]+cost[i][j])
						dp[i][j] = dp[i-1][k]+cost[i][j];
				}
			}
		}
	}
	ans = -1;
	for(i = 1; i <= v; i++)
	{
		if(dp[f][i]>ans)
			ans = dp[f][i];
	}
	printf("%d\n",ans);
	return 0;
}