HDU-4283 You Are the One 题解

题目大意

有n个人，排成一列，每个人有着自己的耐心值$a[i]$，对于每个人来说，他的快乐值等于$a[i]*(j-1)$，j为他是第几个排完队的。你可以用一个类似于栈的东西来控制他们的顺序，让一部分人进去，然后逆序出来。求最小的快乐值。

解题思路

（这道题是真的好难。。。

菜鸡的我，看到这题完全没思路，看完题解写的。。

应该是我目前做过的区间dp最难的题了。。其实也没做多少题。

用$dp[i][j]$来表示区间$[i,j]$中的最小的快乐值。

对于一个区间$[i,j]$来说，我们要想使他最优，那就需要他们的顺序是最优的。

在$[i,j]$区间中，我们将i单独取出来，得到区间$[i+1,j]$。

我们可以枚举这个i插入到的位置。

设这个位置为k，那么就分为了两个区间$[i+1,k]$和$[k+1,j]$。

对于区间$[i+1,k]$来说，他们前面没有人（指在区间$[i,j]$中），所以他的贡献就是$dp[i+1][k]$。

那么对于k这个点来说，因为他的位置为k，原来的位置是i，就相当于是往后面移动了$k-i$位。

那么他的贡献就是$a[i]*(k-i)$。

对于区间$[k+1,j]$来说，就是相当于后移了$k-i+1$位（因为前面有个i），需要加上前面的。

所以他的贡献就是$dp[k+1][j]+(k-i+1)*sum[j]-sum[k]$。

得到区间$[i,j]$的最优解，那么一步步从最小区间$[i,i+1]$开始推，这时候只需要考虑谁先谁后即可。

这样便能推到区间$[1,n]$，得到最终答案$dp[1][n]$。

状态转移方程为$dp[l][r] = min(dp[l][r], dp[l + 1][k] + num[l] * (k - l) + dp[k + 1][r] + (k - l + 1) * (c[r] - c[k]))$。

初始化$dp[i][i]=1$即可，其他的均为INF。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110,INF = 1e9;
int dp[N][N],num[N],c[N];

int main() {
	int t;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> num[i], c[i] = c[i - 1] + num[i];
		for (int i = 1; i <= n; i++) {
			for (int j = i+1; j <= n; j++)  dp[i][j] = INF;
		}
		for (int len = 2; len <= n; len++) {
			for (int l = 1; l <= n - len + 1; l++) {
				int r = l + len - 1;
				for (int k = l; k <= r; k++) {
					int t = dp[l + 1][k] + num[l] * (k - l) + dp[k + 1][r] + (k - l + 1) * (c[r] - c[k]);
					dp[l][r] = min(dp[l][r], t);
				}
			}
		}
		cout << "Case #" << i << ": ";
		cout << dp[1][n] << endl;
	}
}