科技庄园（背包dp）---对于蒟蒻来说死了一大片的奇题

题目描述:

Life种了一块田，里面种了一些桃树。

Life对PFT说：“我给你一定的时间去摘桃，你必须在规定的时间之内回到我面前，否则你摘的桃都要归我吃！”

PFT思考了一会，最终答应了！

由于PFT的数学不好！它并不知道怎样才能在规定的时间获得最大的价值，

由于PFT不是机器人，所以他的体力并不是无限的，他不想摘很多的桃以至体力为0，而白白把桃给Life（如果体力为0，刚刚好回到Life的地点是不行的）。同时PFT每次只能摘一棵桃树，，每棵桃树都可以摘K次（对于同一棵桃每次摘的桃数相同）。每次摘完后都要返回出发点（PFT一次拿不了很多）即Life的所在地（0，0）{试验田左上角的桃坐标是（1，1）}。

PFT每秒只能移动一个单位，每移动一个单位耗费体力1(摘取不花费时间和体力,但只限上下左右移动)。

输入格式:

第一行：四个数为N，M，TI，A 分别表示试验田的长和宽，Life给PFT的时间，和PFT的体力。

下面一个N行M列的矩阵桃田。表示每次每棵桃树上能摘的桃数。

接下来N行M列的矩阵，表示每棵桃最多可以采摘的次数K。

输出格式:

一个数：PFT可以获得的最大的桃个数。

样例输入:

样例输出:

10

思路：（多重背包+二进制优化）的加强版。由于PFT只能走直线，所以当PFT的位置在（i，j）时，PFT到起点的距离是i+j。
又因为PFT的体力与PFT的时间缺一不可，所以只要在时间与体力-1之间取较小值即可。注意：当体力=0时，回到起点是不行的，所以要体力-1。

二进制优化（重点）：

for(int j=;j<=m;j++){

    cin>>s;

    int t=,x=*(i+j);

    if(l[i][j]);{

        while(s>=t) {

            c[++q]=t*x;

            v[q]=t*l[i][j];

            s-=t;

            t*=;//拆成1，2，4，8，16的形式

        }

        c[++q]=x*s;

        v[q]=s*l[i][j];

    }

}

//只要s>=t，则还可以再拆，于是t乘2，s减少t。

上代码（改进过的）：

#include<bits/stdc++.h>

using namespace std;

long long n,m,v[],c[],l[][],k[],t,e,q,s;

int main() {

    cin>>n>>m>>t>>e;

    for(register int i=; i<=n; i++) for(register int j=; j<=m; j++)cin>>l[i][j];

    for(register int i=; i<=n; i++) // register,寄存器,可以加速

        for(register int j=; j<=m; j++) {

            cin>>s;

            int t=,x=*(i+j);

            if(l[i][j]){//二进制优化

                while(s>=t) {

                    c[++q]=t*x;

                    v[q]=t*l[i][j];

                    s-=t;

                    t*=;

                }

                c[++q]=x*s;

                v[q]=s*l[i][j];

            }

        }

    t=min(t,e-);

    for(register int i=;i<=q;i++)for(register int j=t;j>=c[i];j--)k[j]=max(k[j],k[j-c[i]]+v[i]);//01背包就可以了

    cout<<k[t];

    return ;

}

巴特西