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

?

先把掛飾按掛鉤數量從大到小排序

dp[i][j]前i個掛飾，剩下j個掛鉤的最大喜悅值

分掛和不掛轉移

?

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm>using namespace std;#define N 2011int dp[N+1][N];struct node {int sum,val; }e[N];void read(int &x) {x=0; int f=1; char c=getchar();while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }x*=f; }bool cmp(node p,node q) {return p.sum>q.sum; }int main() {int n;read(n);for(int i=1;i<=n;++i){read(e[i].sum);read(e[i].val);}sort(e+1,e+n+1,cmp);memset(dp,-127,sizeof(dp));int inf=dp[0][0];dp[1][1]=0;for(int i=1;i<=n;++i)for(int j=0;j<=n;++j)if(dp[i][j]!=inf){dp[i+1][min(n,j-1+e[i].sum)]=max(dp[i+1][min(n,j-1+e[i].sum)],dp[i][j]+e[i].val);dp[i+1][j]=max(dp[i+1][j],dp[i][j]);}int ans=0;for(int i=0;i<=n;++i) ans=max(ans,dp[n+1][i]);cout<<ans; }

?

4247: 掛飾

Time Limit:?10 Sec??Memory Limit:?256 MB
Submit:?1253??Solved:?507
[Submit][Status][Discuss]

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)

?

?

Source

JOI 2013~2014 春季training合宿 競技4 By PoPoQQQ

?

轉載于:https://www.cnblogs.com/TheRoadToTheGold/p/8213270.html

總結

以上是生活随笔為你收集整理的bzoj千题计划197：bzoj4247: 挂饰的全部內容，希望文章能夠幫你解決所遇到的問題。

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