GCJ 2009 Round1C C Bribe the Prisoners

/*
  这题终于对了，真是感激涕零，痛苦流涕，这个故事告诉我们：
  前人的经验果然是有道理的，INF就不要乱设置了，就设0x3f3f3f3f就好
  
  当然，还有一个问题就是，不要随便设置long long型，因为每次加法的中间结果，都要加 long long 强制类型转换，以避免溢出，会很烦，而且很容易错，比如我把INF改为 long long型以后，我是真的有去给中间结果，都加上强制类型转换的，该改变数据类型的地方，比如t，和dp数组，我也没有用int定义，而是都改long long了，可是仍然incorrect，就很迷...但是我找了好久也不知道哪里出了问题...
  
*/

#include <iostream>
#include <cstdio>
using namespace std;
const int MAX_Q = 1e4 + 10;
const int INF = 0x3f3f3f3f;
int P, Q, A[MAX_Q + 2]; // A中保存输入数据，下标从1开始

// dp[i][j]:= 释放(i, j)所需的金币
//(表示的是，将从A[i]号到A[j]号囚犯(不含两段的囚犯)的连续部分的所有囚犯都释时，所需的最少金币数)
int dp[MAX_Q + 1][MAX_Q + 2];

void solve()
{
	//为了处理方便，将两端加入A中，把左端当作0号囚犯，右端当作 P+1 号囚犯，这样 dp[0][P +1]即为所求
	//之所以这样加入，是因为定义dp[i][j]时候，对两段的处理，是作为开区间处理的 
	A[0] =  0;
	A[Q + 1] = P + 1;
	
	for (int i = 0; i <= Q; i++)
	dp[i][i + 1] = 0;
	
	// 从最短的区间开始填充dp
	for (int w = 2; w <= Q + 1; w++)
	for (int i = 0; i + w <= Q + 1; i++)
	{
		// 计算dp[i][j]
		int j = i + w, t = INF; 
		// 枚举最初释放的囚犯，计算最小的费用
		for (int k = i + 1; k < j; k++)
		t = min(t, dp[i][k] + dp[k][j]);
		
		// 最初的释放还需要与所释放囚犯无关的 A[j] - A[i] - 2枚金币
		dp[i][j] = t + A[j] - A[i] - 2;
	} 
	cout << dp[0][Q + 1] << endl;
} 
int main()
{
	freopen("E:\c2.txt", "r", stdin);
	freopen("E:\out2.txt", "w", stdout);
	int k;
	cin >> k;
	for (int kase = 1; kase <= k; kase++)
	{
		cin >> P >> Q;
		for (int i = 1; i <= Q; i++) cin >> A[i];
		cout << "Case #" << kase << ": ";
		solve();
	}
	fclose(stdin);
	fclose(stdout);
}