Skip to content

记忆化搜索

UVA437

也是一道很好的记忆化搜索的题。

~~刚看到这题时我是懵逼的~~

对于每个块，都能够产生三种状态，并且因为题目说要严格小于，所以这三种状态最多只能放一个，因此所有块的所有状态加一块就只有\(3n\)种。

这大大简化了题目的难度。

由题目我们知道，不会出现两个柱子架桥的情况，每个块上只能放一个块。

下面开始做题。

1) 口胡篇

那么我们可以设\(f[x][y]\)表示下面有长边为\(x\)，短边为\(y\)的方块时，能放的最大高度。

\(x,y\)可能很大? 没关系，因为只有\(3n\)个所以直接离散化。

放方块的顺序就是按照\(x\)和\(y\)为第一、第二关键字排序，这样剪枝稍微提升速度。 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long 
using namespace std;
const int N=310;
int f[N][N],g[N];
int cnt,n;
struct node {
    int x,y,h;
} q[N];
bool Cmp(node a,node b){
    if(a.x==b.x)return a.y>b.y;
    else return a.x>b.x;
}
bool cmp(int a,int b){
    return a<b;
}
void init() {//Discrete 
    memset(f,0,sizeof f);
    int a,b,c;
    for(int i=1; i<=n; ++i) {
        scanf("%lld%lld%lld",&a,&b,&c);
        g[3*i-2]=a,g[3*i-1]=b,g[3*i]=c;
        if(a>b)swap(a,b);
        if(a>c)swap(a,c);
        if(b>c)swap(b,c);
        q[3*i-2].x=c,q[3*i-2].y=b,q[3*i-2].h=a;
        q[3*i-1].x=c,q[3*i-1].y=a,q[3*i-1].h=b;
        q[3*i].x=b,q[3*i].y=a,q[3*i].h=c;
    }

    sort(g+1,g+3*n+1,cmp);
    int tot=unique(g+1,g+3*n+1)-g-1;

    for(int i=1;i<=3*n;++i){
        q[i].x=lower_bound(g+1,g+tot+1,q[i].x)-g;
        q[i].y=lower_bound(g+1,g+tot+1,q[i].y)-g;
    }
    sort(q+1,q+3*n+1,Cmp);
}
int dp(int x,int y,int p){
    if(x<y || x<=0 || y<=0)return 0;
    if(f[x][y])return f[x][y];
    for(int i=p;i<=3*n;++i){
        if(q[i].x<x && q[i].y<y || q[i].y<x && q[i].x<y)f[x][y]=max(f[x][y],dp(q[i].x,q[i].y,i)+q[i].h);
    }
    return f[x][y];
}
signed main() {
    while(1) {
        ++cnt;
        scanf("%lld",&n);
        if(!n)return 0;
        init();
        int ans=0;
        for(int i=1;i<=3*n;++i){
            ans=max(ans,dp(q[i].x,q[i].y,i)+q[i].h);
        }
        printf("Case %lld: maximum height = %lld\n",cnt,ans);
    }
    return 0;
}

2) 正解篇

事实上，状态就只有\(O(n)\)种，设\(f[x]\)表示下面是\(x\)时的最大值。

时间复杂度还是\(O(n^2)\)，空间可变为\(O(n)\)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long 
using namespace std;
const int N=95;
int f[N],g[N];
int cnt,n;
struct node {
    int x,y,h;
} q[N];
bool Cmp(node a,node b){
    if(a.x==b.x)return a.y>b.y;
    else return a.x>b.x;
}
bool cmp(int a,int b){
    return a<b;
}
void init() {//Discrete 
    memset(f,0,sizeof f);
    int a,b,c;
    for(int i=1; i<=n; ++i) {
        scanf("%lld%lld%lld",&a,&b,&c);
        g[3*i-2]=a,g[3*i-1]=b,g[3*i]=c;
        if(a>b)swap(a,b);
        if(a>c)swap(a,c);
        if(b>c)swap(b,c);
        q[3*i-2].x=c,q[3*i-2].y=b,q[3*i-2].h=a;
        q[3*i-1].x=c,q[3*i-1].y=a,q[3*i-1].h=b;
        q[3*i].x=b,q[3*i].y=a,q[3*i].h=c;
    }
    sort(g+1,g+3*n+1,cmp);
    int tot=unique(g+1,g+3*n+1)-g-1;
    for(int i=1;i<=3*n;++i){
        q[i].x=lower_bound(g+1,g+tot+1,q[i].x)-g;
        q[i].y=lower_bound(g+1,g+tot+1,q[i].y)-g;
    }
    sort(q+1,q+3*n+1,Cmp);
}
int dp(int p){
    int x=q[p].x,y=q[p].y;
    if(x<y || x<=0 || y<=0)return 0;
    if(f[p])return f[p];
    for(int i=p;i<=3*n;++i){
        if(q[i].x<x && q[i].y<y)f[p]=max(f[p],dp(i)+q[i].h);
    }
    return f[p];
}
signed main() {
    while(1) {
        ++cnt;
        scanf("%lld",&n);
        if(!n)return 0;
        init();
        int ans=0;
        for(int i=1;i<=3*n;++i){
            ans=max(ans,dp(i)+q[i].h);
        }
        printf("Case %lld: maximum height = %lld\n",cnt,ans);
    }
    return 0;
}
  • 结论：记忆化搜索的时间复杂度基本与空间复杂度一致，只要状态设计没问题，时间上就过得去。

P2476

首先说明\(f[i][j]\)表示前\(i\)个木块已经涂完，最前面的木块颜色为\(j\)的状态设计是错误的，因为同一种状态可能表示多个分支，但有的分支可能存在更多的解不能被搜到，例如前一种分支中\(c[k]==0\),但后一种分支\(c[k]>0\)，可以继续搜索，但是由于记忆化导致直接退出，使得答案变小。

观察到\(c_i\)很小，所以直接设\(f[a][b][c][d][e][last]\)表示有多少个剩\(1,2,3,4,5\)个的颜色且上一次染色是剩\(last\)个的颜色时的贡献。

每次选择一种颜色，那么这种颜色剩余数\(-1\)，比他小\(1\)的颜色数\(+1\),如果\(last\)比他大\(1\)，说明这一轮有一个颜色不能用，所以这一轮总共能取的颜色数\(-1\).

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
const int N=16,M=6,P=1e9+7;
int k,n,ans;
int v[N],vis[M];
int f[N][N][N][N][N][M];
int dfs(int a,int b,int c,int d,int e,int last){
    if(f[a][b][c][d][e][last])return f[a][b][c][d][e][last];
    if(a+b+c+d+e==0)return f[a][b][c][d][e][last]=1;

    int res=0;
    if(a)res=(res+(a-(last==2))*dfs(a-1,b,c,d,e,1)%P)%P;
    if(b)res=(res+(b-(last==3))*dfs(a+1,b-1,c,d,e,2)%P)%P;
    if(c)res=(res+(c-(last==4))*dfs(a,b+1,c-1,d,e,3)%P)%P;
    if(d)res=(res+(d-(last==5))*dfs(a,b,c+1,d-1,e,4)%P)%P;
    if(e)res=(res+e*dfs(a,b,c,d+1,e-1,5)%P)%P;

    return f[a][b][c][d][e][last]=res;
}

signed main(){
    scanf("%lld",&k);
    for(int i=1;i<=k;++i)scanf("%lld",&v[i]),n+=v[i],++vis[v[i]];
    printf("%lld",dfs(vis[1],vis[2],vis[3],vis[4],vis[5],0)%P);
    return 0;
}