题解 P2392 【kkksc03考前临时抱佛脚】

长河落日 · 2018-07-26 10:09:36 · 题解

蒟蒻学不来DP所以第一反应是搜索……

看了一下数据范围

20?emmm

于是放心大胆地2^n枚举了

枚举每道题交给哪边的脑子解决，找到两边时间较大值的最小值

于是愉快地解决了……剪枝都不用放

#include<bits/stdc++.h>
using namespace std;
int Left,Right,minn,ans;
int s[5];
int a[21][5];
void search(int x,int y){
    if(x>s[y]){
        minn=min(minn,max(Left,Right));
        return;
    }
    Left+=a[x][y];
    search(x+1,y);
    Left-=a[x][y];
    Right+=a[x][y];
    search(x+1,y);
    Right-=a[x][y];//毫无技巧的搜索回溯
}
int main(){
    cin>>s[1]>>s[2]>>s[3]>>s[4];
    for(int i=1;i<=4;i++){//减少码量
        Left=Right=0;
        minn=19260817;
        for(int j=1;j<=s[i];j++)
            cin>>a[j][i];
        search(1,i);
        ans+=minn;
    }
    cout<<ans;
    return 0;
}