当前位置:网站首页>Bzoj4247: decoration (DP)

Bzoj4247: decoration (DP)

2020-12-07 14:36:30 osc_ 96wcoyea

Subject portal
.

solution :
Hang the hook first .
Because suppose you choose five pendants in the end .
So it must be the one with more hooks .
Then arrange the order according to the number of hooks .
then Dp Just a moment
f[i][j] Before presentation i We're done ( You don't have to choose everyone ) After that, there is still j Hook .
f[i][j]=max(f[i-1][j],f[i-1][j-a[i].a+1]+a[i].b)






Code implementation :

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
struct node {
  
  int a,b;}a[2100];
bool cmp(node n1,node n2) {
  
  if(n1.a!=n2.a)return n1.a>n2.a;return n1.b>n2.b;}
int f[2100][2100];
int main() {
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].a,&a[i].b);
    sort(a+1,a+1+n,cmp);
    for(int i=0;i<=n;i++)for(int j=1;j<=n+1;j++) f[i][j]=-2000000000;f[0][1]=0;
    for(int i=1;i<=n;i++)for(int j=0;j<=n;j++) {
        f[i][j]=max(f[i-1][j],f[i-1][max(j-a[i].a,0)+1]+a[i].b);
    }
    int ans=0;
    for(int i=0;i<=n;i++)ans=max(ans,f[n][i]);
    printf("%d\n",ans);
    return 0;
}d

版权声明
本文为[osc_ 96wcoyea]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/202012071434170678.html