题解 P2374 【搬运工】
引领天下
2017-11-11 09:01:16
为什么要用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;
}
```