poj 2609 双塔DP-输出路径-用前缀和压缩状态

题目链接：http://poj.org/problem?id=2609
题目大意：有一个长度为m的两个车厢。有一排车，必须按顺序驶入车厢（左右任选）但是不能超过m长度。问最多装多少。如果第i辆车装不下，那么后面的车都不能再装。

思路：用f[i][j][k]:表示前i辆车左车厢长度为j，右车厢长度为k的状态是否存在。因为j+k==sum[i]。所以可以降一维。

#include  <map>
#include  <set>
#include  <cmath>
#include  <queue>
#include  <cstdio>
#include  <vector>
#include  <climits>
#include  <cstring>
#include  <cstdlib>
#include  <iostream>
#include  <algorithm>
using namespace std;

int f[510][15010], g[510][15010];
int a[510], sum[510];
int main() {

    int m; scanf("%d", &m);
    m*=100;
    int n=0, x;
    while(1){
        scanf("%d", &x);
        if(x==0){
            break;
        }
        a[++n]=x;
    }
    for(int i=1; i<=n; i++){
        sum[i]=sum[i-1]+a[i];
    }
    f[0][0]=1;
    int mx=0, sx=0;
    for(int i=0; i<n; i++){
        for(int s=0; s<=15000; s++){
            if(f[i][s]){

                int L=s, R=sum[i]-L;
                if(L+a[i+1]<=m){
                    f[i+1][L+a[i+1]]=1;
                    g[i+1][L+a[i+1]]=1;
                    mx=i+1, sx=L+a[i+1];
                }
                if(R+a[i+1]<=m){
                    f[i+1][L]=1;
                    g[i+1][L]=2;
                    mx=i+1, sx=L;
                }
               //cout<<i<<" "<<s<<endl;
            }
        }
    }
    printf("%d\n", mx);
    vector<char*> ans;
    while(mx){
        if(g[mx][sx]==1){
            ans.push_back("port");
            sx-=a[mx];
            mx--;
        }
        else{
            ans.push_back("starboard");
            mx--;
        }
    }
    for(int i=ans.size()-1; i>=0; i--){
        printf("%s\n", ans[i]);
    }

    return 0;
}