[数据结构与算法]HDU Rise in Price（动态规划）

题目链接：Problem - 6981 (hdu.edu.cn)

题意：从左上角（1，1）走到右下角（N,N）,每个格子有aij个钻石和每个钻石单价增加bij，只能向右或者向下走，走2*n-2步，钻石的初始数目和初始单价都为0。

题解：

dp状态：dp[i][j][k]? ? k表示为到达? i，j?位置有多少种转移状态

dp[i][j][k].first 表示钻石数? ?dp[i][j][k].second表示钻石单价

dp[i][j][k]状态由dp[i-1][j][x]和dp[i][j-1][y]两个状态转移而来，每次转移时选取前一百个大的状态进行转移。

参考：(6条消息) Rise in Price - hdu6981_那页的博客-CSDN博客

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<long long, long long>>  dp[200][200];//dp[i][j][k]表示ij有k中转移状态
int a[200][200];
int b[200][200];
int T;
int n;
bool cmp(pair<long long, long long> a, pair<long long, long long> b)//a和b都大的排前面
{
	return a.first * a.second > b.first* b.second;
}
int main()
{
	cin >> T;
	while (T--)
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				cin >> a[i][j];
				dp[i][j].clear();
			}
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				cin >> b[i][j];
			}
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				if (i == 1 && j == 1)//第一步
				{
					dp[i][j].push_back({ a[i][j], b[i][j] });
					continue;
				}
				else if (i == 1)//第一行只可能由左边一个状态转移
				{
					dp[i][j].push_back(dp[i][j - 1][0]);
				}
				else if (j == 1)//第一列只可能由上面一个状态转移
				{
					dp[i][j].push_back(dp[i - 1][j][0]);
				}
				else
				{
					int p1 = 0;//记录左边一个状态到了第几个
					int p2 = 0; //记录上边一个状态到了第几个
					while (dp[i][j].size() < 100)//存100个状态
					{
						if (p1 < dp[i][j - 1].size() && p2 < dp[i - 1][j].size())
						{
							if (dp[i][j - 1][p1].first * dp[i][j - 1][p1].second >
								dp[i - 1][j][p2].first* dp[i - 1][j][p2].second)
								dp[i][j].push_back(dp[i][j - 1][p1++]);
							else
								dp[i][j].push_back(dp[i - 1][j][p2++]);
						}
						else if (p1 < dp[i][j - 1].size())
						{
							dp[i][j].push_back(dp[i][j - 1][p1++]);
						}
						else if (p2 < dp[i - 1][j].size())
						{
							dp[i][j].push_back(dp[i - 1][j][p2++]);
						}
						else
						{
							break;
						}
					}
				}
					for (int k = 0; k < dp[i][j].size(); k++)//加上当前格子的a,b值
					{
						dp[i][j][k].first += a[i][j];
						dp[i][j][k].second += b[i][j];
					}
					sort(dp[i][j].begin(), dp[i][j].end(), cmp);//a*b大的排前面

			}

		cout << dp[n][n][0].first * dp[n][n][0].second << endl;
	}
}