The Imp Gym - 100543K dp

#include<map>
#include<queue>
#include<time.h>
#include<limits.h>
#include<cmath>
#include<ostream>
#include<iterator>
#include<set>
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep_1(i,m,n) for(int i=m;i<=n;i++)
#define mem(st) memset(st,0,sizeof st)
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef pair<double,double> pdd;
const int N = 150000+10;
#define x first
#define y second
pair<int,int>pos[15];
int num[210];
int dp[N][15];
int cnt=0;
struct node
{
	int v,c;
} e[N];
bool cmp(node a, node b)
{
	return a.v<b.v;
}
void solve()
{
	int n,k;
	cin>>n>>k;
	for(int i=1; i<=n; i++)
		cin>>e[i].v>>e[i].c;
	sort(e+1,e+1+n,cmp);
	memset(dp,0,sizeof dp);
	//dp[i,j] 从i考虑到n 还剩j次魔法次数
	for(int i=n; i; i--)
		for(int j=0; j<=k; j++)
		{
			//只能带一件 md 
			if(j==0)
				dp[i][j]=max(dp[i+1][j],e[i].v-e[i].c);
			else
				dp[i][j]=max(dp[i+1][j],min(e[i].v-e[i].c, dp[i+1][j-1]-e[i].c));
		}
	cout<<dp[1][k]<<endl;
}
signed main()
{
	int t;
	cin>>t;
	while(t--)
		solve();
	return 0;
}

The Imp Gym - 100543K dp

原文：https://www.cnblogs.com/QingyuYYYYY/p/12867209.html