养猪_lduoj_dp

养猪

Description

你有一个猪圈，有N头猪，每天你最多可以杀一头猪卖钱，获益就是猪的体重。但是每过一天每头猪的体重都会下降P[i]（当然，如果猪体重≤0了，自然获利为0），问K天内你的最大获利。

Input

第一行两个数N,K；

第二行N个数，表示猪的初始重量A[i]；

第三行N个数表示P[i]。

Output

一行一个数表示最大获利。

Samples

Input Copy

2 2
10 10
1 2

Output

19

Hint

对于20%的数据，满足1≤N≤20;

对于100%的数据，满足1≤N≤1000，初始重量≤105.

刚开始有一种方法，将输入的数据首先按照体重进行排序，如果体重相同就按照体重减小的程度从大到小进行排序（这样可以在遍历的过程中首先取容易贬值的），这样可以满足一个当前状态来看比较优的情况，然后wa掉了。

上面的方法Wa掉之后以为是在取了一个之后，其余的元素减少的值可能会引起他们大小的改变，所以说写了一个优先队列，定义一种优先的顺序，可以在每次取元素的时候得到当前值最大的，并在每次操作之后将里面的元素减掉一个减少的值，然后重新放到队列里面（用栈stack和优先队列priority_queue），然后还是wa掉了

这时就考虑了方法的正确性：当前这一步的最优会干扰其他的元素的值进行减小，当前的操作会影响后面还没有选过的，并干扰全局最优的情况，所以说要考虑使用动态规划的方法来进行处理该题

在处理数据的时候要注意按照猪体重减小的顺序进行排序，如果说体重减小得快，就要先对他进行处理，如果说体重减小的比较慢就对他进行后处理

因为排序的方法的原因，所以在得到的dp数组中的值可能不会出现在最后面，要遍历数组或者是排序后输出最大元素

ll n , m;
ll ans;
struct node{
    ll x;
    ll y;
}a[1007];
bool cmp(node a,node b){
    if(a.y != b.y) return a.y > b.y;
    else return a.x > b.y;
    /**
    if(a.x != b.x) return a.x > b.x;
    else return a.y > b.y;
    **/
}
ll dp[maxn];
int main()
{
    n = read,m=read;
    for(int  i=1;i<=n;i++) a[i].x = read;
    for(int  i=1;i<=n;i++) a[i].y = read;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){
            ll temp = a[i].x - a[i].y * (j-1);
            if(temp < 0) temp = 0;
            dp[j] = max(dp[j-1] + temp,dp[j]);
        }
    }
    for(int i=1;i<=m;i++) ans = max(ans,dp[i]);
    cout << ans <<endl;
    return 0;
}

文章知识点与官方知识档案匹配，可进一步学习相关知识

算法技能树leetcode-动态规划22-括号生成7688 人正在系统学习中