题解 P2374 【搬运工】

引领天下

2017-11-11 09:01:16

Solution

为什么要用DP呢? 用DFS多好。 每次搜一堆,一直搜下去,找最大值,不就行了吗??? DP多难写啊。 #谨以此题解祝我下午NOIP RP=无限大! 上代码: ```C #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <iostream> using namespace std; int w[4][101],n,i,j,k; long long ans,now;//用long long,防爆 void in(){ scanf ("%d%d%d",&i,&j,&k),n=i+j+k;//n是书的总数,i,j,k为123堆 for (int t=1;t<=i;t++)scanf ("%d",&w[1][t]);//读入书 for (int t=1;t<=j;t++)scanf ("%d",&w[2][t]); for (int t=1;t<=k;t++)scanf ("%d",&w[3][t]); } void dfs(int a,int b,int c){//DFS int x; if (a+b+c==0){ if (now>ans)ans=now; return;//搬完了,更新答案 } x=n-(a+b+c)+1;//搬这本书需要的体力 if (a>0){//如果有才搜 now+=w[1][a]*x;//递归前加 dfs(a-1,b,c);//搬一本(第一堆) now-=w[1][a]*x;//改回去 }//以下原理同上 if (b>0){ now+=w[2][b]*x; dfs(a,b-1,c); now-=w[2][b]*x; } if (c>0){ now+=w[3][c]*x; dfs(a,b,c-1); now-=w[3][c]*x; } } int main(){ in();//读入 dfs(i,j,k);//DFS printf ("%lld",ans);//输出 return 0; } ```