【BestCoder Round #59 (div.1) B】【疯狂的火神】

题目大意

t分钟有n个人可以打，如果在第x分钟单挑这个人（x指单挑完这个人的时间），就会得到a-b*x的经验值。求最大经验值。

解题思路

比较相邻两个人单挑的顺序怎样更优，发现c[i]*b[i+1]>*c[i+1]*b[i]时前后调换更优， 接着就可以dp，f[i][j]=g[j-c[i]]+a[i]-j*b[i]，f[i][j]为打到第i个人用了j分钟的最大经验值，g[i]为至多打到第i-1个人用了至多j分钟的最大经验值。

code

//#include<set> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define LF double #define LL long long #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) using namespace std; int const maxn=1000,maxt=3000; int n,t,a[maxn+10],b[maxn+10],c[maxn+10],f[maxn+10][maxt+10],g[maxt+10]; int main(){ freopen("d.in","r",stdin); freopen("d.out","w",stdout); int tt;scanf("%d",&tt); fo(cas,1,tt){ scanf("%d%d",&n,&t); fo(i,1,n)scanf("%d%d%d",&a[i],&b[i],&c[i]); fo(j,1,n-1) fo(i,1,n-j) if(1ll*c[i]*b[i+1]>1ll*c[i+1]*b[i]){ swap(a[i],a[i+1]); swap(b[i],b[i+1]); swap(c[i],c[i+1]); } memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); fo(i,1,n){ fo(j,c[i],t) f[i][j]=g[j-c[i]]+a[i]-1ll*j*b[i]; fo(j,1,t)g[j]=max(g[j-1],max(g[j],f[i][j])); } printf("%d\n",g[t]); } return 0; }