首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。