题解 P2374 【搬运工】

发表于 更新于 阅读次数： Waline：
P2374 【搬运工】题解。

为什么要用DP呢？

用DFS多好。

每次搜一堆，一直搜下去，找最大值，不就行了吗？？？

DP多难写啊。

#谨以此题解祝我下午NOIP RP=无限大！

上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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;
}