8.18 区间dp+状压dp测试

kamikuQAQ · 2025-08-19 22:56:32 · 个人记录

P1775

随手ac，区间dp板子

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e2+7; 
int dp[maxn][maxn];
int sum[maxn],a[maxn];
signed main(){
    int n;
    cin>>n;
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        dp[i][i]=0; 
    }
    for(int len=2;len<=n;len++) {
        for(int l=1;l+len-1<=n;l++) {
            int r=l+len-1;
            for(int k=l;k<r;k++) {
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
            }
        }
    }
    cout<<dp[1][n];
    return 0;
}

P3205

同样板子，但是注意结尾一定要取模不然100->60

#include<bits/stdc++.h>
using namespace std;
#define mod 19650827
const int maxn = 1e3+7;
int a[maxn],dp[maxn][maxn][2];
signed main() {
    int n;
    cin>>n;
    memset(dp,0,sizeof(dp));
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        dp[i][i][0]=1,dp[i][i][1]=0;
    }
    for(int len=2; len<=n; len++) {
        for(int l=1; l+len-1<=n; l++) {
            int r=l+len-1;
            if(a[l]<a[l+1]) {
                dp[l][r][0]+=dp[l+1][r][0];
            }
            if(a[l]<a[r]) {
                dp[l][r][0]+=dp[l+1][r][1];
            }
            if(a[l]<a[r]) {
                dp[l][r][1]+=dp[l][r-1][0];
            }
            if(a[r]>a[r-1]) {
                dp[l][r][1]+=dp[l][r-1][1];
            }
            dp[l][r][0]%=mod;
            dp[l][r][1]%=mod;
        }
    }
    cout<<(dp[1][n][0]+dp[1][n][1])%mod;
    return 0;
}

U562085

考试时写了bfs假解骗了30pts（）
正解是先跑bfs图算出最短路，然后记录每个电线杆位置转成一维的曼哈顿距离，用状压dp算

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+7;
const int Inf = 0x3f3f3f;
struct Point{
    int x,y;
};
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int n,m,t;
vector<Point>Q;
int dp[17][1<<17];
string s[maxn];
int dis[maxn][maxn];
int f[maxn][maxn];
bool check(int x,int y) {
    if(x>=1&&x<=n&&y>=0&&y<m&&s[x][y]!='#') {
        return 1;
    }
    return 0;
}
void bfs(Point A) {
    queue<Point>q;
    q.push(A);
    memset(dis,0x3f,sizeof(dis));
    dis[A.x][A.y]=0;
    while(!q.empty()) {
        Point u=q.front();
        q.pop();
        for(int i=0;i<4;i++) {
            int dxx=dx[i]+u.x;
            int dyy=dy[i]+u.y;
            if(!check(dxx,dyy)) {
                continue;
            }
            if(dis[dxx][dyy]>dis[u.x][u.y]+1) {
                dis[dxx][dyy]=dis[u.x][u.y]+1;
                q.push({dxx,dyy});
            }
        }
    }
}
int main(){
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++) {
        cin>>s[i];
    }
    int st=0;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<m;j++) {
            if(s[i][j]=='S'||s[i][j]=='T') {
                Q.push_back({i,j});
                if(s[i][j]=='S') {
                    st=Q.size()-1;
                }
            }
        }
    }
    int l=Q.size();
    swap(Q[0],Q[st]);
    for(int i=0;i<l;i++) {
        bfs(Q[i]);
        for(int j=0;j<l;j++) {
            f[i][j]=dis[Q[j].x][Q[j].y];
        }
    } 
    memset(dp,0x3f,sizeof(dp));
    dp[0][1]=0;
    for(int i=0;i<(1<<l);i++) {
        for(int j=0;j<l;j++) {
            if(i>>j&1) {
                for(int k=0;k<l;k++) {
                    dp[j][i]=min(dp[j][i],f[k][j]+dp[k][i^(1<<j)]);
                }
            }
        }
    }
    int res=Inf;
    for(int i=0;i<l;i++) {
        res=min(res,dp[i][(1<<l)-1]+f[i][0]);
    }
    cout<<((res==Inf)?-1:(1ll*(l-1)*t+1ll*res));
    return 0;
}