状态压缩DP解网易雷火笔试题

第一题

假设有n项工作待完成，每项工作都有完成截止日期 deadline，每项工作都会花去cost天，而且不能中断。安排完成工作的顺序，以减少总的工作推迟时间。输入正整数 n(1<=n<=20)，表示工作数量。接下来 n 行，每行包含两个整数，分别表示第 i 项工作的 deadline 和 cost。输出一个数字，表示最少需要推迟几天才能完成所有工作。输入例子1:

输出：2

看了一上午的状态压缩dp算法，大概明白了用该算法的解题思路，其实就是动态规划+位运算。这里记录下，关于算法原理可以参考这里：[模板]二进制状态压缩DP模板（详解_soundwave_的博客-CSDN博客_二进制状态压缩

首先设状态i，代表当前完成任务的状态。比如工作数量为3时，状态可能为：000，001，...，111。1代表这个任务已经完成，0代表未完成。

再设任务j，001，010，100分别代表三个任务。这里画出状态表格如下：

上面的表格第一列为i，第一行为j，根据遍历方程：

    for(int i = 0; i < (1< 
比如当i=0时，也就是当前状态为0，没有完成任意一项工作，这时候和j=1,2,4进行 | 运算，得出下一个状态1，2，4。当i=1时，与j=1进行 & 运算，发现结果不等于0。也就是说在状态等于1时，任务1已经做了，不可能再做一次，所以跳过本次状态。 
if(!(i & (1 << j))) int u = i | (1 << j); 
算出状态后，再计算花费的时间，也就是状态i花费的时间加上新任务花的时间。 
sum[u] = sum[i] + works[j].second; 
最后计算推迟时间，注意每个状态可能有若干个子状态得来，这里要取个最小值。而且同样要加上前面状态推迟的时间。 
dp[u] = min(dp[u], dp[i] + max(0, sum[u] - works[j].first)); 
代码： 
#include 
using namespace std;

int main(int argc, char* argv[]){
    int n;
    cin >> n;
    vector> works(n);
    const int maxn = (1 << n);
    vector dp(1<<20, INT_MAX),sum(1<<20, 0);
    dp[0] = 0;
    for(int i = 0; i < n; i++) cin >> works[i].first >> works[i].second;
    for(int i = 0; i < maxn; i++){
        for(int j = 0; j < n; j++){
            if(!(i & (1 << j))) {
                int u = i | (1 << j);
                sum[u] = sum[i] + works[j].second;
                dp[u] = min(dp[u], dp[i] + max(0, sum[u] - works[j].first));
            }
        }
    }
    cout << dp[maxn-1] << endl;
    return 0;
} 
INT_MIN INT_MAX： #include  
 
第二题 
用红色和绿色两种砖块建一面宽度W高度H的墙，有以下两种砖块可以用。 
红色砖块宽度2，高度1；绿色砖块宽度3，高度1。每种砖块只能按照横向摆放，不能竖起来。横向两块方块之间是有缝的，为了让建好墙更稳固，除了左右两侧以外，避免在任意相邻的两行间，出现上下对齐的砖缝： 
 
下面这两种宽度为3和2的墙也允许 
 
给定一面墙的宽度和高度后，计算在以上规则允许的前提下，一共有多少种不同的建墙方式 
输入：两个整数 W 和 H (2 <= W <= 30, 1 <= H <= 10) 
输出:一个整数，所有可能建墙方式的数量。这个数量可能会大于32位整数的表示范围，请用64位整数 
输入例子: 9 5        输出例子2: 14 
 
以01表示每行的砖块放置方式，w=9 时可以得到下列砌砖方法：
 S1:010101001
 S2:010100101
 S3:010010101
 S4:001010101
 S5:001001001 
先在dfs里算出以上每种可能的状态，然后遍历每个状态 
#include
#include
using namespace std;
int w,h;
vectorstate;
vectorblock = {2,3}; 

void dfs(int pos, int cur_state, vector& state ) {
    if( (1< w )continue;      
            dfs(pos + i, cur_state | (1<< (pos + i)), state);
        }
    }
}
int main() {
    cin >> w >> h;
    dfs(0, 0, state);
    int total_kinds = state.size();     
    vector> dp(h, vector(total_kinds, 0));   //dp[i][j] --代表第i行第j中排列方式可能出现的情况
  
      //第一行无限制，所有每种排列可能出现的情况都是1
    for(int i = 0; i < total_kinds; ++i) {
        dp[0][i] = 1;
    }
    //从第二行开始，遍历每种情况和state库里的情况对比
    for(int i = 1; i < h; ++i) {
        for(int j = 0; j < total_kinds; ++j) {
            for(int k = 0; k < total_kinds; ++k){
                if( (state[j] & state[k]) != (1 << w) )continue;  //将两个状态码位与，除了末尾，还有一处对齐，非法舍弃。
                dp[i][j] += dp[i-1][k];    //合法情况，累加起来
            }
        }
    }
    long long ans = 0;
    for(int i = 0; i < total_kinds; ++i) {
        ans += dp[h-1][i];
    }
    cout<

状态压缩DP解网易雷火笔试题

C/C++/C#相关栏目本月热门文章