2717 - 科技庄园
Life种了一块田，里面种了有一些桃树。
Life对PFT说：“我给你一定的时间去摘桃，你必须在规定的时间之内回到我面前，否则你摘的桃都要归我吃！”
PFT思考了一会，最终答应了！
由于PFT的数学不好！它并不知道怎样才能在规定的时间获得最大的价值，
由于PFT不是机器人，所以他的体力并不是无限的，他不想摘很多的桃以至体力为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可以获得的最大的桃个数。
输入/输出样例
题目输入
4 4 13 20 10 0 0 0 0 0 10 0 0 0 10 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 4 0 0 0 0 0
题目输出
10
提示
【样例解释】 可以摘到1次（1，1）和1次（2，3），体力和时间不满足再摘桃了。 【数据范围】 对于M N TI A 10<=30%<=50 10<=100%<=100 对于K 10<=100%<=100 保证结果在longint范围内
C++解答
#include<iostream> using namespace std; int i,j,k,l,n,m,v,u,g,tim; int f[11000],s[1100][1100],q[1100][1100]; int w[1110000],c[1100000]; int num=1,ans; int main() { //乍一看，有一个想法，这不是一个二维背包咩？ //但这题有个很好的BUG，其实也不算了，就是一个很好玩的条件 //PET童鞋每秒移动一个单位，每移动一个单位耗一点体力 //这就成了01了！ //对了，还有，注意PET童鞋比较那啥，他的路程是要跑两次的！ int t; cin>>n>>m>>tim>>t;//矩阵长 宽 时间 体力 f[0]=0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>s[i][j]; }//能摘的桃数量 } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>q[i][j];//能摘的次数 if(s[i][j]>0)//如果这棵树能摘 { for(int v=num;v<=num+q[i][j];v++) //有一点提醒一下，就是上面那句for循环，注意num的值！ //num是可摘总数 （物品数量！） { w[v]=(i+j)*2;//w[]是花费（可以这么说），就是物体体积了啦！ c[v]=s[i][j]; //提一下，c[]为价值，就不说了哈！ } }num+=q[i][j];//桃纸的总数 } } t=min(t-1,tim);//不多解释 ，前面有讲（应该讲了，没讲提醒一下）； for(i=1;i<=num;i++) for(j=t;j>=w[i];j--) { if(j-w[i]<0) break;//这一部分不解释 else f[j]=max(f[j],f[j-w[i]]+c[i]);//状态转移大方程，不多解释（要解释的童鞋~吱~一声） } cout<<f[t]<<endl; }
提示
【样例解释】 可以摘到1次（1，1）和1次（2，3），体力和时间不满足再摘桃了。 【数据范围】 对于M N TI A 10<=30%<=50 10<=100%<=100 对于K 10<=100%<=100 保证结果在longint范围内