题解 P2374 【搬运工】

引领天下 · 2017-11-11 09:01:16 · 题解

为什么要用DP呢？

用DFS多好。

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

DP多难写啊。

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

上代码：

#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;
}