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;
}
全部评论

相关推荐

时雨h:人生就像站在岔路口,两个方向都可以先了解了解,就像罗伯特·弗罗斯特诗里说的,“黄色的树林里分出两条路,可惜我不能同时去涉足” ,这两个方向就如同那两条路,每条都有独特的风景与未知。 除了自行探索,也可以看看自己学校往年同专业学长学姐的去向,每一届大致都差不多,这能帮你找到自己的定位。多跟他们交流交流,听听他们在不同选择中的收获与遗憾,那些过来人的经验会成为你前行路上的微光。 做出选择后,固然要坚定自己的选择,勇往直前地走下去,但也别忘了,那条未选择的路也始终在那里,它或许代表着另一种可能,另一种人生轨迹。偶尔回望,它能让你更加明白自己当下选择的价值,也能让你在前行的路上,多一份思考与从容。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务