首页 > 代码库 > POJ 2184 Cow Exhibition

POJ 2184 Cow Exhibition

2024-07-12 05:55:41   222人阅读

这题有两个费用，一个是聪明度s，另一个是幽默度f。

可以把其中一个当做体积，另一个当做价值，因为有负数的原因，当做体积的那一个加上1000

dp[i]用来表示体积为i 的最大价值

自己在敲的时候，更新的时候出了问题

 1  for(j=mmax; j>=a; j--) 2                 if(dp[j-a]!=-inf) 3                 { 4                     int n1=cnt[j],n2=cnt[j-a]; 5                     if(dp[j]+j-n1*1000<dp[j-a]+j-a-n2*1000+b) 6                     { 7                         dp[j]=dp[j-a]+b; 8                         cnt[j]=cnt[j-a]+1; 9                     }10 11                 }

红色部分是错误的，红色部分表示的是聪明度为i时，聪明度+幽默度的和最大，但是dp[i]用来表示体积为i 的最大价值，dp[j]用来表示体积为j 的最大价值,所以不可以把j,j-a放进去。

正确的更新应该是

 1 for(j=mmax; j>=a; j--) 2                 if(dp[j-a]!=-inf) 3                 { 4                     int n1=cnt[j],n2=cnt[j-a]+1; 5                     if(dp[j]-n1*1000<dp[j-a]-n2*1000+b) 6                     { 7                         dp[j]=dp[j-a]+b; 8                         cnt[j]=cnt[j-a]+1; 9                     }10 11                 }

还有一个容易出现问题的地方

1             for(i=0; i<=mmax; i++)2             if(dp[i]>=0&&i-cnt[i]*1000>=0)//聪明度和幽默度都不能为负数3             {4                 int tmp=i+dp[i];5                 int nm=cnt[i];6                 tmp-=1000*nm;7                 mm=max(mm,tmp);8             }

绿色的条件不能弄错了

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<set> 6 #include<vector> 7 #include<map> 8 #include<algorithm> 9 #include<cmath>10 #include<stdlib.h>11 using namespace std;12 const int inf = 100000000;13 int dp[210000],cnt[210000];14 int main()15 {16     int i,j,n;17     while(cin>>n)18     {19         for(i=0; i<=200000; i++)20             dp[i]=-inf;21         dp[0]=0;22         memset(cnt,0,sizeof(cnt));23         int mmax=0;24         for(i=1; i<=n; i++)25         {26             int a,b;27             scanf("%d%d",&a,&b);28             a+=1000;29             mmax+=a;30             for(j=mmax; j>=a; j--)31                 if(dp[j-a]!=-inf)32                 {33                     int n1=cnt[j],n2=cnt[j-a]+1;34                     if(dp[j]-n1*1000<dp[j-a]-n2*1000+b)35                     {36                         dp[j]=dp[j-a]+b;37                         cnt[j]=cnt[j-a]+1;38                     }39 40                 }41         }42         int mm=0;43         for(i=0; i<=mmax; i++)44             if(dp[i]>=0&&i-cnt[i]*1000>=0)45             {46                 int tmp=i+dp[i];47                 int nm=cnt[i];48                 tmp-=1000*nm;49                 mm=max(mm,tmp);50             }51 52         cout<<mm<<endl;53     }54 }
View Code

 


联系
我们