[POJ2184] Cow Exhibition

 

题意：有n头牛，每头牛两个元素(s,t)，选择若干头牛使∑s+∑t最大，且∑s、∑t非负

 

题解：

dp(带决策条件的状态)

状态：dp[j]表示s和为j时，t和的最大值

转移：dp[j+s[i]]=max{dp[j]+t[i]} (j>=0)

这样是不行的，因为s[i]会被重复转移，所以要把当前被转移的答案存到另一个数组里

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; }

 

转载于:https://www.cnblogs.com/HLXZZ/p/7510520.html

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的[POJ2184] Cow Exhibition的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。