01背包。把一個(gè)屬性當(dāng)成費(fèi)用，另一個(gè)屬性當(dāng)成價(jià)值。費(fèi)用可能為負(fù)數(shù)，處理的時(shí)候加上100000就可以了。

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std;const int INF=2100000000; const int maxn=100+10; int n; int a[maxn],b[maxn]; int F=100000; int dp[200000+10],tmp[200000+10];int main() {while(~scanf("%d",&n)){for(int i=1; i<=n; i++) scanf("%d%d",&a[i],&b[i]);for(int i=0; i<=2*F; i++) dp[i]=-INF;for(int i=1; i<=n; i++){for(int j=0; j<=2*F; j++) tmp[j]=-INF;tmp[F+a[i]]=b[i];for(int j=0; j<=2*F; j++){if(dp[j]==-INF) continue;int pre=j-F;tmp[pre+a[i]+F]=max(tmp[pre+a[i]+F],dp[j]+b[i]);}for(int j=0; j<=2*F; j++) dp[j]=max(dp[j],tmp[j]);}int ans=0;for(int i=F; i<=2*F; i++)if(dp[i]>=0)ans=max(ans,i-F+dp[i]);printf("%d\n",ans);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zufezzt/p/5350713.html

總結(jié)

以上是生活随笔為你收集整理的POJ 2184 Cow Exhibition的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。