取数字 动态规划

取数字 动态规划

/*
 填表
 先填第一行
 然后一直填到最后一行
 遵循只填大数的原则
 最后输出表尾元素即可 
 */
#define LOCAL
#include<iostream>
#define N 100 
using namespace std;
int a[N][N], opt[N][N];
void nummax(int m, int n)
{
	int i, j;
	opt[0][0] = a[0][0];
	for (i = 1; i < n; i++)
		opt[0][i] = opt[0][i - 1] + a[0][i];
	for (i = 1; i < m; i++)
	{
		opt[i][0] = opt[i - 1][0] + a[i][0];
		for (j = 1; j < n; j++)
			opt[i][j] = a[i][j]
					+ (opt[i - 1][j] > opt[i][j - 1] ?
							opt[i - 1][j] : opt[i][j - 1]);
	}
}
int main()
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int m, n, i, j;
	while (cin >> m >> n)
	{
		for (i = 0; i < m; i++)
			for (j = 0; j < n; j++)
				cin >> a[i][j];
		memset(opt, 0, sizeof(opt));
		nummax(m, n);
		/*
		 for(i=0;i<m;i++)
		 {
		 for(j=0;j<n;j++)
		 {
		 cout<<a[i][j]<<" ";		
		 }	
		 cout<<endl;
		 }
		 for(i=0;i<m;i++)
		 {
		 for(j=0;j<n;j++)
		 {
		 cout<<opt[i][j]<<" ";		
		 }	
		 cout<<endl;
		 }
		 */
		cout << opt[m - 1][n - 1] << endl;
	}
	return 0;
}

发表回复