Problem F. 狂乱
还是一道有点思维难度的DP，和当初的那道射枪游戏差不多....但这个题就没向DP的方向想，光在那干熬着了...任何时候都不能放弃啊！！！
首先，我们可以枚举任何一个随从，对它使用狂乱。接下来的问题就是怎么求解这个随从最多能带走的攻击力的问题。
发现当前随从打的最后一个人有点特殊，因为打的其他随从的伤害都是满的。只有最后一个的时候，你可以和他同归，这样为我们考虑枚举最后一个要打的随从，剩下的随从的攻击模式都是一样的，伤害都是打满的。而且因为我们枚举了最后一个要打的随从，剩下的随从的顺序就无关紧要了。这个时候我们就可以DP了。设f[i][j]表示前i个人，被打了j的体力所带走的最大的攻击力。由于我们枚举的最后一个要打的人将序列分成两部分了，我们还要求一个g[i][j]表示后i个人， 被打了j的体力所带走的最大的攻击力。之后枚举最后一个人，枚举打左边的体力即可。
#include<bits/stdc++.h>
using namespace std;
const int N=105,M=1e4+10;
int n,a[N],b[N],f[N][M],g[N][M],sum;
//f[i][j]表示前i个人被打了j的体力所能带走的最大攻击力
inline int ask(int x,int y)//x把y打死要掉的血量。
{
return ceil(1.0*b[y]/a[x])*a[y];
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&a[i],&b[i]);
sum+=a[i];
}
int ans=0;
for(int i=1;i<=n;++i)//枚举对第i个人使用狂乱。
{
int s1=0;
for(int j=1;j<=n;++j) if(i!=j) s1+=ask(i,j);
if(b[i]>s1)
{//如果当前随从能将所有随从干死，且不死，则无论怎样打，它都存活到最后。
ans=max(ans,sum-a[i]);
continue;
}
for(int j=0;j<=n;++j)
for(int k=0;k<=b[i];++k) f[j][k]=g[j][k]=0;
for(int j=1;j<=n;++j)
{
for(int k=1;k<=b[i];++k)
{
f[j][k]=f[j-1][k];//当前随从不打。
if(i==j) continue;
int d=ask(i,j);
if(k>=d) f[j][k]=max(f[j][k],f[j-1][k-d]+a[j]);
}
}
for(int j=n;j>=1;--j)
{
for(int k=1;k<=b[i];++k)
{
g[j][k]=g[j+1][k];//当前随从不打。
if(i==j) continue;
int d=ask(i,j);
if(k>=d) g[j][k]=max(g[j][k],g[j+1][k-d]+a[j]);
}
}
for(int j=1;j<=n;++j)//枚举最后打的一个人。
{//算出当前随从至少要剩的血量才能与当前随从同归。
if(i==j) continue;
int ds=(ceil(1.0*b[j]/a[i])-1)*a[j]+1;
if(ds>b[i]) continue;
for(int k=0;k<=b[i]-ds;++k)//枚举左边给用的体力。
ans=max(ans,f[j-1][k]+g[j+1][b[i]-ds-k]+a[i]+a[j]);
}
}
printf("%d",sum-ans);
return 0;
}