题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1017
搞了一个下午才弄出来，，，，，
还是线性DP做的不够啊
看过数据量就知道状态转移方程和x，没有关系
然后再仔细推导就会知道整个转移方程只和k与y的差值有关
然后继续推导。。。。
定义dp[i][j]表示表示第j步删除最上边的i点，
定义mv[i]表示删除i点的同时可以向下移动的最远位置(可以预处理出来)
那么dp[i][j]=max(dp[i-1][j],dp[i-mv[i]][j-1]+mv[i]);
状态转移方程表示dp[i][j],如果删除i点那么其等于dp[i-mv[i]][j-1]+mv[i](顺便把能删除的全删除)
如果不删除i点，那么dp[i][j]=dp[i-1][j]；取他们中的最大值。
代码：
1 #include<iostream> 2 #include<cstdlib> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 #define maxn 110 8 int f[maxn]; 9 int tol=0; 10 int n,w,k; 11 int mv[maxn]; 12 int dp[maxn][maxn]; 13 int main() 14 { 15 int t; 16 scanf("%d",&t); 17 int iCase=1; 18 while(t--) 19 { 20 scanf("%d%d%d",&n,&w,&k); 21 memset(dp,0,sizeof(dp)); 22 memset(mv,0,sizeof(mv)); 23 int tmp; 24 for(int i=0;i<n;i++) 25 scanf("%d%d",&tmp,&f[i]); 26 sort(f,f+n); 27 for(int i=n-1;i>=0;i--) 28 { 29 int high=i,low=i; 30 while(f[high]-f[low]<=w&& low>=0) low--; 31 mv[i]=high-low; 32 } 33 for(int i=0;i<n;i++) 34 for(int j=1;j<=k;j++) 35 if(i>=mv[i]) 36 dp[i][j]=max(dp[i-1][j],dp[i-mv[i]][j-1]+mv[i]); 37 else dp[i][j]=mv[i]; 38 cout<<"Case "<<iCase++<<": "<<dp[n-1][k]<<endl; 39 } 40 return 0; 41 }