USACO Section 1.3 Barn Repair - 卡了一年的DP...

/*
ID: zzyzzy12
LANG: C++
TASK: barn1
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int M,S,C,i,a[205],b[205],dp[201][51],k,j,ans;
int main()
{
     freopen("barn1.in","r",stdin);
     freopen("barn1.out","w",stdout);
     scanf("%d%d%d",&M,&S,&C);      
     for (i=1;i<=C;i++) scanf("%d",&a[i]); 
     sort(a+1,a+1+C); 
     memset(dp,0x7F,sizeof(dp));   
     dp[1][1]=1;
     for (k=2;k<=C;k++)
     {
          dp[k][1]=1+a[k]-a[1]; 
          for (i=2;i<=min(M,k);i++) 
          {
                if (dp[k][i]>dp[k-1][i]+a[k]-a[k-1])
                   dp[k][i]=dp[k-1][i]+a[k]-a[k-1];  
                if (dp[k][i]>dp[k-1][i-1]+1) dp[k][i]=dp[k-1][i-1]+1;
          }   
     }
     ans=2000000000;
     for (i=1;i<=M;i++) ans=ans<dp[C][i]?ans:dp[C][i];     
     printf("%d\n",ans);
     return 0;  
}