uva11598 Optimal Segments（DP 求方案）

#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
struct cell{
    string str;
    int value;
}c[35];
int t,N,K;
int dp[35][35][18];
int path[35][35],sum[35];
vector<int> v;
int high,low,ans;
void init(){
    memset(dp,-1,sizeof dp);
    v.clear();
    ans=1000000000;
    sum[0]=0;
}
void input(){
    scanf("%d%d",&N,&K);
    for(int i=1;i<=N;i++){
        cin>>c[i].str;
        if(c[i].str=="X") sum[i]=sum[i-1]+1,c[i].value=0;
        else{
            stringstream s1;
            s1<<c[i].str;
            s1>>c[i].value;
            sum[i]=sum[i-1];
        }
    }
}
int DP(int x,int y,int k){
    if(k==1){
        int check=0;
        for(int i=x;i<=y;i++){
            if(c[i].str=="X") {check=1;break;}
        }
        if(check){
            int sum=0;
            for(int i=x;i<=y;i++){
                sum+=c[i].value;
            }
            v.push_back(sum);
            vector<int> a=v;
            int nn=a.size();
            sort(a.begin(),a.end());
            if(a[nn-1]-a[0]<=ans){
                low=a[0],high=a[nn-1];
                ans=a[nn-1]-a[0];
            }
            v.pop_back();
        }
        return check;
    }
    if(dp[x][y][k]==0) return dp[x][y][k];
    int start_X=-1,now=0;
    for(int i=x;i<=y;i++){
        if(c[i].str=="X") {start_X=i;break;}
        now+=c[i].value;
    }
    if(start_X==-1) return dp[x][y][k]=0;
    int ret=0,tmp;
    for(int i=start_X;i<=y;i++){
        now+=c[i].value;
        v.push_back(now);
        if(!DP(i+1,y,k-1)){
            v.pop_back();
            continue;
        }
        v.pop_back();
        ret=1;
    }
    return dp[x][y][k]=ret;
}
ll cal(int x){return 1LL<<x;}
bool judge(int x,int y,int k){
    if(k==0) return 1;
    int now=0;
    for(int i=x;i<=y-k+1;i++) now+=c[i].value;
    bool ret=0;
    for(int i=y-k+1;i>=x;i--){
        if(now<=high&&now>=low&&sum[i]-sum[x-1]>=1){
            if(judge(i+1,y,k-1)){
                path[x][y]=i,ret=1;
                break;
            }
        }
        now-=c[i].value;
    }
    return ret;
}
void output(int x,int y,int k){
    printf("(");
    for(int i=x;i<=path[x][y];i++){
        if(i>x) printf(" ");
        printf("%s",c[i].str.c_str());
    }
    printf(")");
    if(k>1) output(path[x][y]+1,N,k-1);
}
void solve(){
    if(!DP(1,N,K)){
        printf("not possible!\n");
    }else{
        if(ans>=50){
            printf("overflow\n");
        }else{
            printf("%lld ",cal(ans));
            judge(1,N,K);
            output(1,N,K);
            printf("\n");
        }
    }
}
int main(){
    //freopen("test.txt","r",stdin);
    scanf("%d",&t);
    for(int ca=1;ca<=t;ca++){
        init();
        input();
        printf("Case %d: ",ca);
        solve();
    }
    return 0;
}