C++版本
//poj 3390
//sep9
#include <iostream>
#include<memory.h>
using namespace std;
const int maxM=102;
const int maxN=10004;
int dp[maxN+1][maxM+1];
int L[maxN];
int main()
{
int cases;
scanf("%d",&cases);
while(cases--){
int m,n,s;
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
scanf("%d",&L[i]);
memset(dp,0x7f,sizeof(dp));
dp[0][m]=0;
for(int i=1;i<=n;i++){
int x=dp[maxN][maxM];
for(s=m;s>=0;--s)
x=min(x,dp[i-1][s]);
dp[i][L[i]]=x+(m-L[i])*(m-L[i]);
for(s=L[i]+2;s<=m;++s){
int x=s-L[i]-1;
if(dp[i-1][x]==dp[maxN][maxM])
continue;
int y=dp[i-1][x]-(m-x)*(m-x)+(m-s)*(m-s);
dp[i][s]=y;
}
}
int ans=dp[0][maxM];
for(s=0;s<=m;++s)
ans=min(ans,dp[n][s]);
printf("%d\n",ans);
}
return 0;
}
c语言版本
#include<stdio.h>
#include<memory.h>
#define maxM 108
#define maxN 10004
int f[maxM+10][maxN+10];
int L[maxN+1];
int min(int a,int b){
if(a>b)
return b;
else
return a;
}
int main()
{
int c,i,x,y,fine;
scanf("%d",&c);
while(c--){
int m,n,s;
scanf("%d%d",&m,&n);
for(i=1;i<=n;++i)
scanf("%d",&L[i]);
memset(f,0x7f,sizeof(f));
f[0][m]=0;
for(i=1;i<=n;i++){
x=f[maxM][maxN];
for(s=m;s>=0;s--)
x=min(x,f[i-1][s]);
f[i][L[i]]=x+(m-L[i])*(m-L[i]);
for(s=L[i]+2;s<=m;s++){
x=s-L[i]-1;
if(f[i-1][x]==f[maxM][maxN])
continue;
y=f[i-1][x]-(m-x)*(m-x)+(m-s)*(m-s);
f[i][s]=y;
}
}
fine=f[maxM][maxN];
for(s=0;s<=m;s++){
fine=min(fine,f[n][s]);
}
printf("%d\n",fine);
}
return 0;
}