1 solutions
-
0
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; }
Pascal :
program skyline; var w,c,t:array[1..10000]of longint; f:array[0..100]of longint; num:array[1..100,1..100]of longint; n,m,ti,a,i,j,k,tot,time:longint; begin { assign(input,'manor.in');reset(input); assign(output,'manor.out');rewrite(output);} readln(n,m,ti,a); dec(a); if ti<a then a:=ti; for i:=1 to n do for j:=1 to m do read(num[i,j]); for i:=1 to n do for j:=1 to m do begin read(time); if (num[i,j]>0)and(time>0) then begin inc(tot); w[tot]:=(i+j)*2; c[tot]:=num[i,j]; t[tot]:=time; end; end; for i:=1 to tot do for j:=a downto w[i] do for k:=1 to t[i] do if (j>=w[i]*k)and(f[j-w[i]*k]+c[i]*k>f[j]) then f[j]:=f[j-w[i]*k]+c[i]*k; writeln(f[a]); {close(input);close(output);} end.
- 1
Information
- ID
- 757
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By