luoguP2967 [USACO09DEC]视频游戏的麻烦Video Game Troubles

题目

---

f(i,j)表示前i个游戏平台花费j的最大愉悦值。

难点在于保证买该平台游戏，则游戏平台一定要买。

如果按照金明的预算方案那样对于每个附属品选/不选肯定要T。

考虑f(i,j)=max( f(i-1,j-x)+y , f(i-1,j) )，这里x和y是一个附属物品的体积和价值。

如果直接这么转移就会出现不买平台直接买游戏的尴尬。

因此我们考虑先强制买平台。下文中平台价格为p

f(i,j)=f(i-1,j-p)

对于一个平台的附属游戏，只有买了平台才能生效。所以从p+x开始转移

f(i,j)=max(f(i,j),f(i,j-x)+y)      p+x<=j<=v

然后考虑不买的情况

f(i,j)=max(f(i,j),f(i-1,j))

如果直接开f(i,j)数组，空间要爆。显然f(i)只与f(i-1)有关，滚动数组。

code

#include<bits/stdc++.h>
#define N 60
#define V 100010
#define max(a,b) ((a)>(b)?(a):(b))
#define fsb(a,b,c) for(register int a=b;a<=(c);a++)
#define fbs(a,b,c) for(register int a=b;a>=(c);a--)
using namespace std;
int f[2][V],nw=1,lt=0,n,g,v,x,y,p,ans=0;
template<typename qw>inline void rll(qw &x){
 qw f=1;x=0;char c=getchar();
 while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
}
int main(){
 rll(n);rll(v);memset(f,0,sizeof(f));
 fsb(i,1,n){
  rll(p);
  fsb(i,p,v)f[nw][i]=f[lt][i-p];
  rll(g);
  fsb(i,1,g){
   rll(x);rll(y);
   fbs(i,v,p+x)f[nw][i]=max(f[nw][i],f[nw][i-x]+y);
  }
  fsb(i,0,v)f[nw][i]=max(f[nw][i],f[lt][i]);
  swap(lt,nw);
 }
 fsb(i,0,v)ans=max(ans,f[lt][i]);
 printf("%d\n",ans);
 return 0;
}