#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int maxq = 100+10; const int inf = 0x3f3f3f3f; //待释放囚犯的位置 int a[maxq]; //dp[i][j] 释放第 i 个和第 j 个之间所有囚犯所需金币 //这里的认为把需要释放的囚犯单独提取出来 //也就是说，i j 是 Q 里的序号 int dp[maxq][maxq]; int main () { //P 牢房总数， Q 待释放的囚犯数 int P, Q; while(~scanf("%d %d", &P, &Q)){ for(int i= 1; i<= Q; i++) scanf("%d", a+i); //为了处理方便，将两端加入 Q 中 //此时dp[0][Q+1] 就是答案 a[0] = 0, a[Q+1] = P+1; //初始化 //其实主要是为了初始化 dp[i][i+1]的值 memset(dp, 0, sizeof(dp)); //从小到达枚举长度 for(int k= 2; k<= Q+1; k++){ //枚举区间起点 for(int i= 0; i+k<= Q+1; i++){ int temp = inf; //枚举区间内先释放的犯人 for(int j= i+1; j< i+k; j++){ if(temp > dp[i][j] + dp[j][i+k]) temp = dp[i][j] + dp[j][i+k]; } //释放第一个犯人时要给两边无关的犯人发金币 dp[i][i+k] = temp + a[i+k] - a[i] - 2; } } printf("%d\n", dp[0][Q+1]); } return 0; }
