洛谷 P1622 释放囚犯
题目传送门：https://www.luogu.com.cn/problem/P1622
转换为石子的合并问题。
区间DP+四边形优化。
#include
#include
using namespace std;
const int MAXQ = 105;
const int INF = 0x7fffffff;
int dp[MAXQ][MAXQ]; //dp[i][j]表示：把第i堆到第j堆合并，需要的成本
int s[MAXQ][MAXQ]; //s[i][j]表示：第i堆到第j堆，最好的分割点
int a[MAXQ];
int num[MAXQ];
int sum[MAXQ];
int initData(int p,int q){
for(int i=1;i>a[i]; //输入堆的分割点
}
a[q+1] = p+1;
for(int i=1;i<=q+1;i++){
num[i] = a[i] - a[i-1] - 1; //第i堆的人数
sum[i] = sum[i-1] + num[i]; //前i堆的人数（不包括被释放的罪犯）
}
for(int i=1;i>p>>q;
initData(p,q);
//一共q+1堆
for(int len=1;len<=q;len++){
for(int start = 1;start+len<=q+1;start++){
int end = start + len;
dp[start][end] = INF;
for(int k = s[start][end-1];k dp[start][k] + dp[k+1][end] + sum[end] - sum[start-1] + len -1){
dp[start][end] = dp[start][k] + dp[k+1][end] + sum[end] - sum[start-1] + len -1;
s[start][end] = k;
}
}
}
}
cout<<dp[1][q+1]<<endl;
return 0;
}
作者：Together2020
