?

題意：有n頭牛，每頭牛兩個元素(s,t)，選擇若干頭牛使∑s+∑t最大，且∑s、∑t非負(fù)

?

題解：

dp(帶決策條件的狀態(tài))

狀態(tài)：dp[j]表示s和為j時，t和的最大值

轉(zhuǎn)移：dp[j+s[i]]=max{dp[j]+t[i]} (j>=0)

這樣是不行的，因?yàn)閟[i]會被重復(fù)轉(zhuǎn)移，所以要把當(dāng)前被轉(zhuǎn)移的答案存到另一個數(shù)組里

tmp[j+s[i]]=max{dp[j]+t[i]}

?

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #define ll long long using namespace std;int dp[100010],tmp[100010];struct Node {int s,t;bool operator < (Node x) const {return s>x.s;} }p[110];int gi() {int x=0,o=1; char ch=getchar();while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();if(ch=='-') o=-1,ch=getchar();while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return o*x; }int main() {int n=gi(),S=n*1000,ans=0,inf;for(int i=1; i<=n; i++) {p[i].s=gi(),p[i].t=gi();}sort(p+1,p+n+1);memset(dp,-63,sizeof(dp));inf=dp[0],dp[0]=0;for(int i=1; i<=n; i++) {for(int j=0; j<=S; j++) tmp[j]=dp[j];for(int j=S; j>=0; j--) {if(dp[j]==inf) continue;if(j+p[i].s>=0) {tmp[j+p[i].s]=max(dp[j+p[i].s],dp[j]+p[i].t);}}for(int j=0; j<=S; j++) dp[j]=tmp[j];}for(int i=0; i<=S; i++) {if(dp[i]<0) continue;ans=max(ans,dp[i]+i);}printf("%d", ans);return 0; }

?

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

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

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

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