codeforces QDU - 133

https://qduoj.com/problem/133

和hdu 3466一個套路

觀察ai−di∗ti 因為每個題的分數都和時間有關 所有有個先後次序問題 并且ai di ci三個參數中ai與時間無關 不做考慮 

假設有兩個物品(d1 c1)和(d2 c2) 先解決1再解決2的代價是-(d1*c1)-(d2*(c1+c2)) 先解決2再解決1的代價是-(d2*c2)-(d1*(c1+c2)) 肯定是要選擇代價小的方案 是以在排序就按-(d1*c1)-(d2*(c1+c2))>-(d2*c2)-(d1*(c1+c2)) 化簡一下就是c1*d2<c2*d1

#include <bits/stdc++.h>
using namespace std;
const int N=0x3f3f3f3f;
const int maxn=2e3+10;
const int maxs=5e3+10;

struct node
{
    int a,d,c;
};

node item[maxn];
int dp[maxs];
int n,s;

bool cmp(node n1,node n2)
{
    return n1.c*n2.d<n2.c*n1.d;
}

int main()
{
    int i,j,ans;
    scanf("%d%d",&n,&s);
    for(i=1;i<=n;i++){
        scanf("%d",&item[i].a);
    }
    for(i=1;i<=n;i++){
        scanf("%d",&item[i].d);
    }
    for(i=1;i<=n;i++){
        scanf("%d",&item[i].c);
    }
    sort(item+1,item+n+1,cmp);
    for(i=0;i<=s;i++){
        dp[i]=-N;
    }
    dp[0]=0;
    for(i=1;i<=n;i++){
        for(j=s;j>=item[i].c;j--){
            dp[j]=max(dp[j],dp[j-item[i].c]+item[i].a-j*item[i].d);
        }
    }
    ans=-N;
    for(i=0;i<=s;i++){
        ans=max(ans,dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}