首页 > 代码库 > hdu 4293 区间DP

hdu 4293 区间DP

 1 /* 2 题目大意:n个人分成若干组,每个人都描叙他们组前面有多少人后面有多少人, 3 求说真话的人最多有多少个。 4 解题思路:把同一组的人数统计起来他们组前面有x人后面有y人, 5 num[x+1][n-y]表示区间[x+1,n-y]的权值,num[x+1][n-y]<=n-x-y 6 那么就是求不重合,[1,n]区间的最大值 7 */ 8 #include <iostream> 9 #include <cstdio>10 #include <cstring>11 using namespace std;12 13 const int maxn=505;14 int dp[maxn],num[maxn][maxn];15 inline int max(int a,int b){return a>b?a:b;}16 17 int main()18 {19     int n,i,j,x,y;20     while(~scanf("%d",&n))21     {22         memset(num,0,sizeof(num));23         memset(dp,0,sizeof(dp));24         for(i=1;i<=n;i++)25         {26             scanf("%d%d",&x,&y);27             if(num[x+1][n-y]<n-x-y)28                 num[x+1][n-y]++;29         }30         int ans=0;31         for(i=1;i<=n;i++)32         {33             for(j=0;j<i;j++)34                 dp[i]=max(dp[i],dp[j]+num[j+1][i]);35             ans=max(ans,dp[i]);36         }37         printf("%d\n",ans);38     }39     return 0;40 }

 

hdu 4293 区间DP