D、E、F

dp

D - A Spy in the Metro

题意：

• 某城市的地铁有$n$个车站 编号$1$到$n$ 有$m1$辆车向右开 给出$m1$个从车站$1$出发的时间 ，$m2$辆车向左开 给出$m2$个从车站$n$出发的时间，$t[i]$为火车从第$i$个车站开到第$i+1$（或相反）个车站需要的时间 Maria在车站$1$ 她需要恰在时刻$T$到达第$n$个车站 求她的最小总车站等待时间。

解题思路：

• 紫书上的原题。对于一个状态来说有三种转移方式：$1$、原地等待一分钟。$2$、搭乘往右的车（若有） $3$、搭乘往左开的（若有），注意边界条件dp[n] [T]=0，其余都为INF。

代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string.h>
#include<stdio.h>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=250+5;
const double eps=1e-4;
typedef long long ll;
typedef pair<int,ll> pil;
int dp[N][N];
int t[N];
bool h[2*N][N][2];
int main()
{
    int n;
    int tot=1;
    while(~scanf("%d",&n))
    {
        if(n==0)
            break;
        int T;
        memset(h,0,sizeof(h));
        memset(t,0,sizeof(t));
        memset(dp,0,sizeof(dp));
        scanf("%d",&T);
        for(int i=1;i<n;i++)
            dp[T][i]=inf;
        dp[T][n]=0;
        for(int i=1;i<n;i++)
            scanf("%d",&t[i]);
        int tep,m1,m2;
        scanf("%d",&m1);
        for(int i=1;i<=m1;i++)
        {
            scanf("%d",&tep);
            for(int j=1;j<=n;j++)
            {
                h[tep][j][0]=1;
                tep+=t[j];
            }
        }
        scanf("%d",&m2);
        for(int i=1;i<=m2;i++)
        {
            scanf("%d",&tep);
            for(int j=n;j>=1;j--)
            {
                h[tep][j][1]=1;
                tep+=t[j-1];
            }
        }
        for(int i=T-1;i>=0;i--)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=dp[i+1][j]+1;
                if(j<n&&i+t[j]<=T&&h[i][j][0])
                    dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]);
                if(j>1&&i+t[j-1]<=T&&h[i][j][1])
                    dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]);
            }
        }
        printf("Case Number %d: ",tot++);
        if(dp[0][1]>=inf)
            printf("impossible\n");
        else
            printf("%d\n",dp[0][1]);
    }
    return 0;
}

E - The Tower of Babylon

题意：

• 有$n$种立方体，每种都有无限个。要求选一些立方块堆成一根尽量高的柱子（可自行选哪一条边作为高），保证每个立方体的底面长宽分别严格小于它下面立方体的底面长宽。

解题思路：

• 一个长宽高的可以组合成$6$个不同的形式，把这些记录下来以后按照长x宽的大小排个序，然后就是等于求个最长上升序列就行了。

代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string.h>
#include<stdio.h>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=250+5;
const double eps=1e-4;
typedef long long ll;
typedef pair<int,ll> pil;
int dp[N];
struct po
{
    int x,y,z;
}p[N];
bool cmp(po a,po b)
{
    return a.x*b.y<b.x*b.y;
}
int cnt;
void add(int x,int y,int z)
{
    p[cnt].x=x;
    p[cnt].y=y;
    p[cnt++].z=z;
    p[cnt].x=x;
    p[cnt].y=z;
    p[cnt++].z=y;
    p[cnt].x=y;
    p[cnt].y=x;
    p[cnt++].z=z;
    p[cnt].x=y;
    p[cnt].y=z;
    p[cnt++].z=x;
    p[cnt].x=z;
    p[cnt].y=x;
    p[cnt++].z=y;
    p[cnt].x=z;
    p[cnt].y=y;
    p[cnt++].z=x;
}
int main()
{
    int tot=1;
    int n;
    while(scanf("%d",&n))
    {
        if(n==0)
            break;
        cnt=0;
        for(int i=0;i<n;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
        }
        sort(p,p+cnt,cmp);
        memset(dp,0,sizeof(dp));
        int ma=-inf;
        for(int i=0;i<cnt;i++)
        {
            dp[i]=p[i].z;
            for(int j=0;j<i;j++)
            {
                if(p[i].x>p[j].x&&p[i].y>p[j].y)
                    dp[i]=max(dp[i],dp[j]+p[i].z);
            }
            ma=max(ma,dp[i]);
        }
        printf("Case %d: maximum height = %d\n",tot++,ma);
    }
    return 0;
}

F - Unidirectional TSP

题意：

• 给一个$m$行$n$列的整数矩阵，从第一列任何一个位置开始出发每次往右、右上、右下走一格，最终到达最后一列。要求经过的整数之和最小。整个矩阵是环形的，即第一行的上一行是最后一行，最后一发也同理。输出路径上的每列的行号，多解时输出字典序最小的。

解题思路：

• 每一列就是一个状态，每个状态有三种转移方式：右、右下、右上。因为在记录最小值的同时又要求字典序最小，所以在计算的同时也要记下 下一列行号的最小值。

代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string.h>
#include<stdio.h>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=200+5;
const double eps=1e-4;
typedef long long ll;
typedef pair<int,ll> pil;
int dp[N][N];
int a[N][N];
int path[N][N];
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        int ans=inf;
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        memset(dp,inf,sizeof(dp));
        for(int i=1;i<=n;i++)
            dp[i][m]=a[i][m];
        for(int i=m;i>=2;i--)
        {
            for(int j=1;j<=n;j++)
            {
                int rows[3]={j-1,j,j+1};
                if(j==1)
                    rows[0]=n;
                else if(j==n)
                    rows[2]=1;
                sort(rows,rows+3);
                for(int k=0;k<3;k++)
                {
                    int temp=dp[j][i]+a[rows[k]][i-1];
                    if(temp<dp[rows[k]][i-1])
                    {
                        dp[rows[k]][i-1]=temp;
                        path[rows[k]][i-1]=j;
                    }
                }
            }
        }
        int cnt;
        for(int i=1;i<=n;i++)
        {
            if(dp[i][1]<ans)
                ans=dp[i][1],cnt=i;
        }
        printf("%d",cnt);
        for(int j=1,i=path[cnt][j];j<m;j++,i=path[i][j])
            printf(" %d",i);
        printf("\n");
        printf("%d\n",ans);
    }
    return 0;
}