題目大意：
切水果游戲，在屏幕上任意時(shí)刻，你可以切掉屏幕上所有的水果。如果切掉的水果數(shù)大于2，那所得分就是水果數(shù)，否則為0.
給n個(gè)水果序列[st,et]出現(xiàn)時(shí)間和結(jié)束時(shí)間，問最后最多能獲得多少分。
DP+離散化（不懂什么叫離散化！）
dp[i]=max{dp[j-1]+cute[j,i],1<=j<=i}
以開始時(shí)間遞增排序求cute[j,i]
#include<stdio.h>
#include<string.h>
#include<math.h>
int x[1005],y[1005],dp[1005];
int n,ans;
void qxsort(int l,int r)
{
int i,j,mid,tmp;
i=l;
j=r;
mid=x[(i+j)/2];
while (i<=j)
{
while (x[i]<mid) i++;
while (x[j]>mid) j--;
if (i<=j)
{
tmp=x[i];
x[i]=x[j];
x[j]=tmp;
tmp=y[i];
y[i]=y[j];
y[j]=tmp;
i++;
j--;
}
}
if (l<j) qxsort(l,j);
if (i<r) qxsort(i,r);
}
int max(int a,int b)
{
if (a>b)
return a;
return b;
}
void work()
{
int i,j,s,now;
memset(dp,0,sizeof(dp));
qxsort(1,n);
ans=0;
for (i=3;i<=n ;i++ )
{
if (i+1<=n && x[i]==x[i+1]) continue;
s=0;
for (j=i;j>=1 ;j-- )
{
if (x[j]<=x[i] && y[j]>=x[i]) s++;
now=s;
if (now<3)
now=0;
dp[i]=max(dp[i],dp[j-1]+now);
}
ans=max(ans,dp[i]);
}
}
int main()
{
int t,i,cas=0;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (i=1;i<=n ;i++ )
scanf("%d%d",&x[i],&y[i]);
work();
printf("Case #%d: %d\n",++cas,ans);
}
return 0;
}
哎，真是弱爆了，看來dp題目真的很多很變態(tài)啊。要多想想了
還是，問題本質(zhì)很重要！！！！