dtoj#4374. 「BJOI2019」光线

题目描述：

当一束光打到一层玻璃上时，有一定比例的光会穿过这层玻璃，一定比例的光会被反射回去，剩下的光被玻璃吸收。

设对于任意 $x$，有 $x\times a_i\%$ 单位的光会穿过它，有 $x\times b_i\%$ 的会被反射回去。

现在 $n$ 层玻璃叠在一起，有 $1$ 单位的光打到第 $1$ 层玻璃上，那么有多少单位的光能穿过所有 $n$ 层玻璃呢？

 思路：

背包问题

$f_{i,j}$ 表示选到前 $i$ 座城堡已经用了 $j$ 个士兵所能获得总分的最大值。

倘若直接枚举每座城堡派几个士兵效率是 $O(nm^{2})$ ，但是我们发现只有多获胜一个人才能使总分增多，所以我们可以考虑枚举每座城堡赢几个人，效率变成 $O(nms)$ 。

 代码：

#include<bits/stdc++.h>
#define il inline
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
const int N=105,M=2e4+5;
int n,s,m,a[N][N],f[M];
il int read(){
   int x,f=1;char ch;
   _(!)ch=='-'?f=-1:f;x=ch^48;
   _()x=(x<<1)+(x<<3)+(ch^48);
   return f*x;
}
int main()
{
    s=read();n=read();m=read();
    for(int i=1;i<=s;i++)for(int j=1;j<=n;j++)a[j][i]=read()*2+1;
    for(int i=1;i<=n;i++)sort(a[i]+1,a[i]+1+s);
    for(int i=1;i<=n;i++)for(int j=m-1;j>=0;j--){
        for(int k=1;k<=s;k++){
            if(a[i][k]+j>m)break;
            f[a[i][k]+j]=max(f[a[i][k]+j],f[j]+k*i);
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++)ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}

View Code