DP的序--Codeforces956E. Wardrobe

$n \leq 10000$个盒子，有高度，高度总和$\leq 10000$，盒子有重要的和不重要的，问最多有多少重要盒子的底端在区间$[L,R]$。

这是个入门级的DP，但需要一点胆量MD这题能放DIV1E。。

放盒子顺序：不重要的，重要的，然后乱放。不重要的可以无脑放，但重要的需要一定的顺序。。

其实重要的盒子按从大到小的顺序无脑叠就行了。。为啥。。

如果是在$L$处的话，那大的堆下面可以把小的送上去；如果是在$L,R$间，那顺序无所谓；如果是在$R$处，先大再小肯定不优，但我们是在01背包，因此大的那个完全可以丢掉。。

有个小问题，底端算答案有点难，不如把整个问题倒过来用顶端算贡献。

为啥这题都不会啊有没有大佬来拯救一下QAQ

 #include<stdio.h>

 #include<string.h>

 #include<stdlib.h>

 //#include<math.h>

 //#include<queue>

 //#include<vector>

 #include<algorithm>

 #include<iostream>

 //#include<assert.h>

 using namespace std;

 int n,L,R,H;

 #define maxn 10011

 int f[maxn],a[maxn],la=,b[maxn],lb=,c[maxn];

 bool cmp(const int &a,const int &b) {return a>b;}

 int main()

 {

     scanf("%d%d%d",&n,&L,&R);

     for (int i=;i<=n;i++) scanf("%d",&c[i]),H+=c[i];

     L^=R^=L^=R; L=H-L; R=H-R;

     for (int i=,x;i<=n;i++) {scanf("%d",&x); if (x) b[++lb]=c[i]; else a[++la]=c[i];}

     for (int i=;i<=H;i++) f[i]=-0x3f3f3f3f; f[]=;

     for (int i=;i<=la;i++)

         for (int j=H;j>=a[i];j--)

             f[j]=max(f[j],f[j-a[i]]);

     sort(b+,b++lb,cmp);

     for (int i=;i<=lb;i++)

         for (int j=H;j>=b[i];j--)

             f[j]=max(f[j],f[j-b[i]]+(L<=j && j<=R));

 //    for (int i=0;i<=H;i++) cout<<f[i]<<' ';cout<<endl;

     int ans=;

     for (int i=;i<=H;i++) ans=max(ans,f[i]);

     printf("%d\n",ans);

     return ;

 }

巴特西

DP的序--Codeforces956E. Wardrobe

最新文章

热门文章