4247: 掛飾

Time Limit: 1 Sec??

Memory Limit: 256 MB

題目連接

http://www.lydsy.com/JudgeOnline/problem.php?id=4247

Description

JOI君有N個裝在手機上的掛飾，編號為1...N。 JOI君可以將其中的一些裝在手機上。 JOI君的掛飾有一些與眾不同——其中的一些掛飾附有可以掛其他掛件的掛鉤。每個掛件要么直接掛在手機上，要么掛在其他掛件的掛鉤上。直接掛在手機上的掛件最多有1個。 此外，每個掛件有一個安裝時會獲得的喜悅值，用一個整數來表示。如果JOI君很討厭某個掛飾，那么這個掛飾的喜悅值就是一個負數。 JOI君想要最大化所有掛飾的喜悅值之和。注意不必要將所有的掛鉤都掛上掛飾，而且一個都不掛也是可以的。

Input

第一行一個整數N，代表掛飾的個數。 接下來N行，第i行(1<=i<=N)有兩個空格分隔的整數Ai和Bi，表示掛飾i有Ai個掛鉤，安裝后會獲得Bi的喜悅值。

Output

輸出一行一個整數，表示手機上連接的掛飾總和的最大值

Sample Input

5
0 4
2 -2
1 -1
0 1
0 3

Sample Output

5

HINT

將掛飾2直接掛在手機上，然后將掛飾1和掛飾5分別掛在掛飾2的兩個掛鉤上，可以獲得最大喜悅值4-2+3=5。
1<=N<=2000
0<=Ai<=N(1<=i<=N)
-10^6<=Bi<=10^6(1<=i<=N)

題意

?

題解：

背包問題,dp[i][j]表示在考慮第i個物品的時候，還剩下j個掛鉤

注意，要按照掛鉤多少排序，如果不排序的話，掛鉤有可能會變成負數，然后又被加成正數

代碼抄自：http://blog.csdn.net/creationaugust/article/details/48133509?

代碼：

//qscqesze #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <bitset> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define maxn 4051 #define mod 10007 #define eps 1e-9 int Num; //const int inf=0x7fffffff; //нчоч╢С const int inf=0x3f3f3f3f; inline ll read() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } //**************************************************************************************struct node {int x,y; }; bool cmp(node a,node b) {return a.x>b.x; } node a[maxn]; ll dp[maxn>>1][maxn]; int main() {int n=read();for(int i=0;i<=n;i++)dp[0][i]=dp[i][n+1]=-inf;for(int i=1;i<=n;i++)a[i].x=read(),a[i].y=read();sort(a+1,a+1+n,cmp);ll ans=0;dp[0][1]=0;for(int i=1;i<=n;i++){for(int j=0;j<=n;j++){dp[i][j]=max(dp[i-1][max(j-a[i].x,0)+1]+a[i].y,dp[i-1][j]);}}for(int i=0;i<=n;i++)ans = max(ans,dp[n][i]);printf("%d\n",ans); }

?

總結

以上是生活随笔為你收集整理的BZOJ 4247 挂饰 背包DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。