紫书第九章-动态规划初步 刷题总结

Author Avatar
Llf0703 5月 26, 2018
  • 在其它设备中阅读本文章

很久没写过总结了。紫书做了那么多道题，但是我的动规并没有找到什么感觉，也就只有普及难度的可以不看题解写，剩下的都是看着题解写完的，我还是太弱了。这里还是来总结一下吧。

例题

9-1 UVa1025-A Spy in the Metro

$f[i][j]$表示在车站i，时刻是j，还剩多少时间（根紫书略有不同）

决策有三个，上左边的车，上右边的车，如果都不开往幼儿园就等一时刻的车。

注意还要判断某一时刻是否有车，$havel[i][t]$和$haver[i][t]$表示在i车站在t时刻是否有车。

#include<bits/stdc++.h>
using namespace std;

int n,m,t,a,b,c,tright,tleft,Time,cnt;
int T[55],tl,tr,f[55][255];//在车站i，时刻j，还剩多少时间
bool havel[55][255],haver[55][255];//在车站i，在t时刻是否有车

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int main()
{
    while (1)
    {
        memset(havel,false,sizeof(havel));
        memset(haver,false,sizeof(haver));
        memset(f,0,sizeof(f));
        memset(T,0,sizeof(T));
        n=read(); if (n==0) break; t=read();
        for (int i=1;i<n;i++) T[i]=read();
        tright=read();
        for (int i=1;i<=tright;i++)
        {
            tr=read();
            Time=tr;
            for (int j=1;j<=n;j++) haver[j][Time]=true,Time+=T[j];
        }
        tleft=read();
        for (int i=1;i<=tleft;i++)
        {
            tl=read();
            Time=tl;
            for (int j=n;j>=1;j--) havel[j][Time]=true,Time+=T[j-1];
        }
        for (int i=1;i<=n-1;i++) f[i][t]=2e9;
        f[n][t]=0;
        for (int j=t-1;j>=0;j--)
            for (int i=1;i<=n;i++)
            {
                f[i][j]=f[i][j+1]+1;
                if (i>1 && havel[i][j] && j+T[i-1]<=t) f[i][j]=min(f[i][j],f[i-1][j+T[i-1]]);//左
                if (i<n && haver[i][j] && j+T[i]<=t) f[i][j]=min(f[i][j],f[i+1][j+T[i]]);//右
            }
        printf("Case Number %d: ",++cnt);
        if (f[1][0]>=2e9) printf("impossible\n");
        else printf("%d\n",f[1][0]);
    }
    return 0;
}

9-2 UVa437-The Tower of Babylon

长和宽都会严格减小，直接记忆化搜索即可。

用$f[id][h]$表示第id个立方体，第h个数据做高。需要将每个立方体的三维按从小到大排序。

#include<bits/stdc++.h>
#define Ans f[id][h]
using namespace std;

int n,m,a,b,c,h[4],f[40][4],ans,cnt;
bool vis[40][4];
struct Edge{
    int x,y,z;
} edge[35];

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int dp(int id,int h)
{
    if (vis[id][h]) return Ans;
    vis[id][h]=1;
    int E[2],hnow;
    if (h==1) E[0]=edge[id].y,E[1]=edge[id].z,hnow=edge[id].x;
    if (h==2) E[0]=edge[id].x,E[1]=edge[id].z,hnow=edge[id].y;
    if (h==3) E[0]=edge[id].x,E[1]=edge[id].y,hnow=edge[id].z;//判断当前哪两个数据做底面，哪一个是高
    for (int i=1;i<=n;i++)
    {
        if (edge[i].x<E[0] && edge[i].y<E[1]) Ans=max(Ans,dp(i,3)+hnow);
        if (edge[i].x<E[0] && edge[i].z<E[1]) Ans=max(Ans,dp(i,2)+hnow);
        if (edge[i].y<E[0] && edge[i].z<E[1]) Ans=max(Ans,dp(i,1)+hnow);
    }
    return Ans;
}

int main()
{
    for (;;)
    {
        memset(f,0,sizeof(f));
        memset(vis,0,sizeof(vis));
        ans=0;
        n=read();
        if (n==0) break;
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=3;j++) h[j]=read();
            sort(h+1,h+4);
            edge[i].x=h[1]; edge[i].y=h[2]; edge[i].z=h[3];
            for (int j=1;j<=3;j++) f[i][j]=h[j];
        }
        for (int i=1;i<=n;i++)
            for (int j=1;j<=3;j++) ans=max(ans,dp(i,j));
        printf("Case %d: maximum height = %d\n",++cnt,ans);
    }
    return 0;
}

9-3 UVa1347-Tour

将题目的走法改成两个人同时从左边出发，$f[i][j]$表示$1-max(i,j)$全部走过，且两人位置为i和j，还要走多少距离。可以定义i>j，并且只允许走到i+1这个点。

决策就有两个：走到$f[i+1][j]$和$f[i+1][i]$

#include<bits/stdc++.h>
using namespace std;

double f[1005][1005];
int n,m,a,b,c,x[1005],y[1005];

inline double dis(int i,int j)
{
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}

int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        memset(f,0,sizeof(f));
        for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
        for (int i=1;i<n-1;i++) f[n-1][i]=dis(n-1,n)+dis(i,n);
        for (int i=n-2;i>=2;i--)
            for (int j=1;j<i;j++) f[i][j]=min(f[i+1][j]+dis(i,i+1),f[i+1][i]+dis(j,i+1));
        cout<<fixed<<setprecision(2)<<f[2][1]+dis(1,2)<<endl;
    }
    return 0;
}

以上更新于2018.5.26

9-4 UVa116-单向TSP

用$f[i][j]$来记录从起点到$(i,j)$的开销（和紫书上反过来了），注意边界判断就行了。唯一有点难度的就是输出路径，我感觉用的是有点像前向星的方法。

#include<bits/stdc++.h>
using namespace std;
int f[105][105],t[105][105],rd[105][105],newf[105];
int n,m;

int main()
{
    while (~scanf("%d%d",&m,&n))
    {
        for (int i=1;i<=m;i++)
            for (int j=1;j<=n;j++) scanf("%d",&t[i][j]);
        int ans=1e9, last=0;
        for (int i=1;i<=m;i++) f[i][n]=t[i][n];
        if (n==1)
        {
            for (int i=1;i<=m;i++)
                if (f[i][1]<ans) ans=f[i][1],last=i;
        }
        else
        {
            for (int j=n-1;j>=1;j--)
                for (int i=1;i<=m;i++)
                {
                    int dir[]={i,i+1,i-1};
                    if (i==1) dir[2]=m;
                    if (i==m) dir[1]=1;
                    sort(dir,dir+3);
                    f[i][j]=f[dir[0]][j+1]+t[i][j];
                    rd[i][j]=dir[0];
                    for (int k=1;k<3;k++)
                        if (f[dir[k]][j+1]+t[i][j]<f[i][j]) f[i][j]=f[dir[k]][j+1]+t[i][j],rd[i][j]=dir[k];
                    if (j==1 && f[i][j]<ans) ans=f[i][j],last=i; 
            }
        }
            printf("%d",last);
            for (int i=rd[last][1],j=2;j<=n;i=rd[i][j],j++) printf(" %d",i);
            printf("\n%d\n",ans);
    }
    return 0;
}

9-5 UVa12563-劲歌金曲

数据范围真的假，直接01背包即可

#include<bits/stdc++.h>
using namespace std;

int n,m,t,a,b,c,k,kase,sum,ans;
int cnt[55][10005],f[55][10005],s[55];

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int main()
{
    k=read();
    while (k--)
    {
        n=read(); t=read();
        for (int i=1;i<=n;i++) s[i]=read();
        for (int i=1;i<=n;i++) 
            for (int j=0;j<=t;j++)
            {
                cnt[i][j]=(i==1) ? 0 : cnt[i-1][j];
                f[i][j]=(i==1) ? 0 : f[i-1][j];
                if (j>s[i])
                {
                    if (cnt[i][j]<cnt[i-1][j-s[i]]+1) 
                    {
                        cnt[i][j]=cnt[i-1][j-s[i]]+1;
                        f[i][j]=f[i-1][j-s[i]]+s[i];
                    }
                    else if (cnt[i][j]==cnt[i-1][j-s[i]]+1) f[i][j]=max(f[i][j],f[i-1][j-s[i]]+s[i]);
                }
            }
        printf("Case %d: %d %d\n",++kase,cnt[n][t]+1,f[n][t]+678);
    }
}

未完待续

以上内容更新于2018.7.3

9-6 UVa11400-照明系统设计

跟书上的思路一样。每种灯泡要么都取，要么都不取。然后用一个类似LIS的动规方法，用$f[i]$表示前i种灯泡的最小开销，$sum[i]$表示前i种灯泡的数量$f[i]=min(f[i],f[j]+(sum[i]-sum[j])*node[i].c+node[i].k)(j<i)$

#include<bits/stdc++.h>
using namespace std;

struct Node{
    int v,k,c,l;
} node[1005];
int n,m,a,b,sum[1005],f[1005];

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

inline bool cmp(Node a,Node b)
{
    return a.v<b.v;
}

int main()
{
    for (;;)
    {
        n=read();
        if (n==0) break;
        for (int i=1;i<=n;i++) node[i].v=read(),node[i].k=read(),node[i].c=read(),node[i].l=read();
        sort(node+1,node+n+1,cmp);
        for (int i=1;i<=n;i++) sum[i]=node[i].l+sum[i-1];
        f[0]=0;
        for (int i=1;i<=n;i++)
        {
            int now=0x7fffffff;
            for (int j=0;j<i;j++) now=min(now,f[j]+(sum[i]-sum[j])*node[i].c+node[i].k);
            f[i]=now;
        }
        printf("%d\n",f[n]);
    }
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/aoapc-book-9.html