【DP+折半搜索】happy happy happy

动态规划DP, 枚举、搜索

传送门：HDU6196

思路：

  • 直接折半搜索比较好想，然而常数较大会TLE；
  • 考虑到是搜索，可以进行最优性剪枝，用dp求出$mx_{l,r},mn_{l,r}$即可

代码如下：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define N 1000000
LL t,n,rnd,sum,xb,ans,a[100],cnt[N],nxt[N],c[N],mx[100][100],mn[100][100],head[100][100];
int upper(LL x){
    int l=1,r=xb,ret=-1;
    while (l<=r){
        int mid=(l+r)>>1;
        if (c[mid]>x){ret=mid; r=mid-1;} else l=mid+1;
    }
    return ret;
}
void dfs1(int cs,int l,int r,LL tmp){
    if (cs>rnd){cnt[++xb]=tmp; nxt[xb]=head[l][r]; head[l][r]=xb; return;}
    if (a[l]>=a[r]){tmp+=a[l]; dfs1(cs+1,l+1,r-1,tmp); dfs1(cs+1,l+2,r,tmp);}
    else{tmp+=a[r];    dfs1(cs+1,l+1,r-1,tmp); dfs1(cs+1,l,r-2,tmp);}
}
void dfs2(int cs,int l,int r,LL tmp){
    if (cs>rnd){
        int k=upper(sum/2-tmp);
        if (k>0 && (c[k]+tmp)*2-sum<ans) ans=(c[k]+tmp)*2-sum;
        return;
    }
    if (tmp+mx[l][r]+c[xb]<=sum/2 || (tmp+mn[l][r]+c[1])*2-sum>=ans) return;
    if (a[l]>=a[r]){tmp+=a[l]; dfs2(cs+1,l+1,r-1,tmp); dfs2(cs+1,l+2,r,tmp);}
    else{tmp+=a[r]; dfs2(cs+1,l+1,r-1,tmp); dfs2(cs+1,l,r-2,tmp);}
}
int main(){
    while (~scanf("%lld",&n)){
        rnd=n/2/3; ans=INF; sum=0;
        for (int i=1;i<=n;i++){scanf("%lld",&a[i]); sum+=a[i];}
        memset(mx,0,sizeof mx); memset(mn,INF,sizeof mn);
        for (int i=1;i<n;i++){mx[i][i+1]=max(a[i],a[i+1]); mn[i][i+1]=max(a[i],a[i+1]);}
        for (int i=2;i*2<=n;i++)
            for (int j=1;j+i*2-1<=n;j++){
                int k=j+i*2-1;
                if (a[j]>=a[k]){
                    mx[j][k]=max(mx[j+1][k-1]+a[j],mx[j+2][k]+a[j]);
                    mn[j][k]=min(mn[j+1][k-1]+a[j],mn[j+2][k]+a[j]);
                }
                else{
                    mx[j][k]=max(mx[j+1][k-1]+a[k],mx[j][k-2]+a[k]);
                    mn[j][k]=min(mn[j+1][k-1]+a[k],mn[j][k-2]+a[k]);
                }        
            }
        memset(head,0,sizeof head); xb=0; dfs1(1,1,n,0); rnd=n/2-rnd;
        for (int i=1;i+rnd/2-1<=n;i++){
            int j=i+rnd*2-1;
            xb=0; for (int k=head[i][j];k;k=nxt[k]) c[++xb]=cnt[k];
            if (rnd==n/2) c[++xb]=0;
            sort(c+1,c+xb+1);
            if (xb>0) dfs2(1,i,j,0);
        }
        if (ans==INF) puts("The child will be unhappy...");
        else printf("%lld\n",ans);
    }
    
    return 0;
}