SSOJ 监狱

监狱"/>

SSOJ 监狱

题目描述

Tangwan王国中有一个奇怪的监狱，这个监狱里一共有P间牢房，这些牢房一字排开，从左到右按1到P进行编号，第i间后面紧挨着第（i+1）间（最后一间除外）。现在有P名罪犯被关押在这P间牢房里。

某一天，上级下发了一个释放名单，要求每天释放名单上的一个人。这可把监狱中的看守们吓得不轻，因为看守们知道，现在牢房中的P个人，可以相互之间传话。如果某个人离开了，那么原来和这个人能够传上话的人都会很气愤，导致他们那天会一直大吼大叫，搞得看守们很是头疼，但是如果给这些要发火的人吃上肉，他们就会安静。

现在看守们想知道，如何安排释放的顺序，才能使得他们花费的肉钱最少。

输入

第一行两个整数P和Q（Q≤P，1≤P≤1000，1≤Q≤100），Q表示释放名单上人数；

第二行是Q个用空格隔开的整数，表示要释放哪些监狱中的罪犯。

输出

仅一行，一个整数，表示最少要给多少人次送肉吃。

样例输入

20 3
3 6 14

样例输出

35

提示

【样例说明】

先释放14号监狱中的罪犯，要给1到13号监狱和15到20号监狱中的19人送肉吃；再释放6号监狱中的罪犯，要给1到5号监狱和7到13号监狱中的12人送肉吃；最后释放3号监狱中的罪犯，要给1到2号监狱和4到5号监狱中的4人送肉吃。

【注意事项】

Q<=P;且50%的数据1<=P<=100;1<=Q<=5。 

显然是区间DP，但似乎并不好做

我们考虑倒着做，即把区间的分解转化为合并，就符合了我们一般做区间DP时的思想（就像石子合并）。

然后写代码时要考虑合并的区间时，对于合并的两个区间我们要加上两个区间时释放的的犯人，具体看代码。

#include<bits/stdc++.h>
const int N = 1010;
using namespace std;
int n, m, sum[N], dp[N][N], a[N];
int main()
{scanf("%d %d", &n, &m);for(int i = 1; i <= m; i++){scanf("%d",&a[i]);}a[0] = 0;a[++m] = n + 1;sort(a, a + m + 1);for(int i = 1; i <= m; i++){sum[i] = a[i] - a[i - 1] - 1 + sum[i - 1];}for(int i = 2; i <= m; i++){for(int l = 1; l + i - 1 <= m; l++){int r = l + i - 1;//cout<<l<<" "<<r<<endl;for(int x = l; x < r; x++){if(!dp[l][r] || dp[l][r] > dp[l][x] + dp[x + 1][r] + sum[r] - sum[l - 1] + r - l - 1){dp[l][r] = dp[l][x] + dp[x + 1][r] + sum[r] - sum[l - 1] + r - l - 1;}}}}printf("%d", dp[1][m]);return 0;
}