24.8.18 DP训练

exut / 2024-08-18 / 原文

A - Mondriaan's Dream

求用 $1\times 2$ 的小矩形填满 $n\times m$ 的矩形的方案数

sol

数据范围超级小，考虑状压

记录 $st_i$ 表示 $i$ 这个二进制状态下的连续 $0$ 长度是否存在奇数

设 $dp_{i,j}$ 表示到第 $i$ 列，且在 $j$ 中 $1$ 的位置和 $i+1$ 列放了横的小方块

然后转移见代码

#include<cstdio>
#include<iostream>
#define int long long
using namespace std;
const int N=13,L=1<<12;
int dp[N][L];
bool st[L];
int n,m;
void init(){
    for(int i=0;i<(1<<n);i++){
        int cnt=0;
        st[i]=1;
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                if(cnt&1) break;
                cnt=0;
            }
            else cnt++;
        }
        if(cnt&1) st[i]=0;
        for(int j=1;j<=m;j++) dp[j][i]=0;
    }
}

signed main(){
    while(1){
        cin>>n>>m;
        if(n*m%2==1){
            cout<<0<<"\n";
            continue;
        }
        if(n==0 and m==0) return 0;
        init();
        dp[0][0]=1; 
        for(int i=1;i<=m;i++){
            for(int j=0;j<(1<<n);j++){
                for(int k=0;k<(1<<n);k++){
                    if((j&k) or !st[j|k]) continue;
                    dp[i][j]+=dp[i-1][k];
                }
            }
        }
        cout<<dp[m][0]<<"\n";
    }
}

B - Greedy Pie Eaters P

luogu有，题意略去

考虑区间dp，这道题一看就很区间dp不是吗

考虑转移，用一般的区间地爬的套路用 $f(i,j)=sol(f(i,k-1),f(k+1,j))$ 其中 $sol$ 是一些操作

这里设 $p(k,i,j)$ 表示牛子里面能在 $k$ 没吃时吃 $k$ 且 $i\le l \le k\le r\le j$ 的最大的 $w$

预处理 $p$ 然后 $f(i,j)=max(f(i,k-1)+f(k+1,j)+p(k,i,j))$

#include<bits/stdc++.h>
using namespace std;
int n,m;
int dp[305][305];
int p[305][305][305];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int w,l,r;
        cin>>w>>l>>r;
        for(int j=l;j<=r;j++){
            p[j][l][r]=w;
        }
    }
    for(int k=1;k<=n;k++){
        for(int i=k;i;i--){
            for(int j=k;j<=n;j++){
                if(i!=1) 
                    p[k][i-1][j]=max(p[k][i][j],p[k][i-1][j]);
                if(j!=n)
                    p[k][i][j+1]=max(p[k][i][j],p[k][i][j+1]);
            }
        }
    }
    for(int i=n;i>=1;i--){
		for(int j=i;j<=n;j++){

			for(int k=i;k<=j;k++){
				dp[i][j]=max(dp[i][j],(k!=i?dp[i][k-1]:0)+(k!=j?dp[k+1][j]:0)+p[k][i][j]);
			}
		}
	}    cout<<dp[1][n];
}