洛谷状压DP做题记录

拼搏现实的明天。 2023-06-04 07:59 17阅读 0赞

# P2915 \[USACO08NOV\]奶牛混合起来Mixed Up #

[题面][Link 1]

确实是状压的入门题 用dp\[i\]\[j\] 表示以i结尾，状态为j时的方案数，代码如下：

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    const int N=20;
    int n,k;
    int s[maxn];
    long long dp[N][maxn];
    long long ans;
    int maxx;
    int main(){
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++) scanf("%d",&s[i]);
        for(int i=0;i<n;i++) dp[i][1<<i]=1;//初始化
        maxx=1<<n;//最大的状态数
        for(int st=0;st<maxx;st++){
        //枚举可行的状态
            for(int i=0;i<n;i++){
                if(st&(1<<i)){
        //该状态是否合法
                    for(int j=0;j<n;j++){
                        if(!(st&(1<<j))&&abs(s[i]-s[j])>k){
        //按题目条件判断
                            dp[j][st|(1<<j)]+=dp[i][st];
                        }
                    }
                }
            }
        }
        for(int i=0;i<n;i++){
            ans+=dp[i][(1<<n)-1];
        }
        printf("%lld\n",ans);
        return 0;
    }

# P1171 售货员的难题 #

[题面][Link 2]

同样是用状压的方式，dp\[i\]\[j\]表示当前在第i个城市，状态为j的最短路，开了O2

// luogu-judger-enable-o2
    #include<bits/stdc++.h>
    using namespace std;
    const int N=25;
    const int maxn=1100010;
    int dp[N][maxn];//在第i个城市，所走过的城市集合j 
    int g[N][N]; 
    int n;
    int ans=2e9;
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&g[i][j]);
            }
        }
         memset(dp,88,sizeof(dp));
        dp[1][1]=0;
        for(int k=0;k<=(1<<n)-1;k++){
            for(int i=1;i<=n;i++){
                if(((1<<i-1)&k)){
                    for(int j=1;j<=n;j++){
                        if( !( (1<<j-1)&k) ){
                            dp[j][k|(1<<j-1)]=min(dp[j][k|(1<<j-1)],dp[i][k]+g[i][j]);
                        }
                    }
                }
            }
        }
        for(int i=2;i<=n;i++) ans=min(dp[i][(1<<n)-1]+g[i][1],ans);
        printf("%d\n",ans);
        return 0;
    }

#  P3052 \[USACO12MAR\]摩天大楼里的奶牛 #

[题面][Link 3]

其实这道题数据范围一眼看出就是状压DP，但考虑到我们如何进行状态的设计与转移，在状压DP中一定有一维表示的是当前的状态，而在该题中我们对于状态的定义就是dp\[i\]\[j\]表示开了i个电梯，在j状态下的重量，一开始dp数组设为正无穷，在DP的时候找到不为正无穷的状态来进行更新，而还有一个贪心的思路就是没有超限的话就一直往里面塞，这样可以保证分组组数是最少的。最后扫一遍，如果满足开了某几个电梯，并且在最大状态下（全部都装进去）不为正无穷，直接输出即可。

代码（看了题解）

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=3e6+7;
    const int INF=0x7fffffff;
    int w[maxn];
    int n,k;
    int maxx;
    int dp[20][maxn];
    int main(){
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++) scanf("%d",&w[i]);
        maxx=1<<n;
        for(int i=0;i<n;i++){
            for(int j=0;j<maxx;j++){
                dp[i][j]=INF;
            }
        }
        for(int i=0;i<n;i++) dp[1][1<<i]=w[i];
        for(int i=0;i<=n;i++){
            for(int s=0;s<maxx;s++){
                if(dp[i][s]!=INF){
                    for(int t=0;t<n;t++){
                        if(s&(1<<t)) continue;
                        if(dp[i][s]+w[t]<=k){
                            dp[i][s|(1<<t)]=min(dp[i][s|(1<<t)],dp[i][s]+w[t]);
                        }
                        else dp[i+1][s|(1<<t)]=min(dp[i+1][s|(1<<t)],w[t]);
                    }
                }
            }
        }
        for(int i=0;i<=n;i++){
            if(dp[i][maxx-1]!=INF){
                printf("%d\n",i);
                return 0;
            } 
        }
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11223989.html

[Link 1]: https://www.luogu.org/problemnew/show/P2915
[Link 2]: https://www.luogu.org/problemnew/show/P1171
[Link 3]: https://www.luogu.org/problemnew/show/P3052