题意：有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#include #include #include #include #include #define ll long longusing 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;}