挂饰

NC53265. 挂饰

描述

题目译自 JOISC 2014 Day4 T3「ストラップ」

JOI君有N个装在手机上的挂饰，编号为 $1 \ldots N$ 。JOI君可以将其中一些挂饰装在手机上。
JOI君的挂饰有一些与众不同——其中的一些挂饰附有挂钩，你可以将其他挂饰挂在挂钩上。i号挂饰有 $A_i$ 个挂钩。每个挂件要么直接挂在手机上，要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有1个。
此外，每个挂件有一个安装时会获得的喜悦值，用一个整数来表示。如果JOI君很讨厌某个挂饰，那么这个挂饰的喜悦值就是一个负数。
JOI君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰，而且一个都不挂也是可以的。

输入描述

第一行一个整数N，代表挂饰的个数。
接下来N行，第i行有两个空格分隔的整数和，表示挂饰i有个挂钩，安装后会获得的喜悦值。

输出描述

输出一行，一个整数，表示手机上连接的挂饰总和的最大值。

示例1

输入:

输出:

说明:

挂饰2直接挂在手机上，然后将挂饰1和挂饰5分别挂在挂饰2的两个挂钩上，可以获得最大喜悦值4-2+3=5。

示例2

输入:

输出:

说明:

允许一个挂饰都不挂。

示例3

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 19ms, 内存消耗: 16220K, 提交时间: 2020-08-31 10:49:55

#include<bits/stdc++.h>
#define turn_on_clock clock_t start,end;start=clock();
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define turn_off_clock end=clock();printf("\nTime eclipse:%.5lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
using namespace std;
const int N=1e3+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const double PI=atan(1.0)*4.0;
struct Node{
	int a,b;
	bool friend operator<(Node x,Node y){
		if(x.a!=y.a)return x.a>y.a;
		return x.b>y.b;
	}
}p[2005];
int n,dp[2005][2005];
int main(){	
	Fox;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>p[i].a>>p[i].b;
	sort(p+1,p+1+n);
	for(int i=0;i<=2001;i++)
		for(int j=0;j<=2001;j++)dp[i][j]=-2e9-1000;
	dp[0][1]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++)dp[i][j]=max(dp[i][j],dp[i-1][max(0,j-p[i].a)+1]+p[i].b);
		for(int j=0;j<=n;j++)dp[i][j]=max(dp[i][j],dp[i-1][j]);
	}
	/*
	for(int i=1;i<=n;i++,cout<<"\n")
		for(int j=0;j<=n;j++)
			cout<<dp[i][j]<<" ";
	*/
	int ans=0;
	for(int i=0;i<=n;i++)ans=max(ans,dp[n][i]);
	cout<<ans;
	return 0;
}

/*
3
2 -2
0 4
0 3
*/