程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 10817 狀態壓縮DP

uva 10817 狀態壓縮DP

編輯：C++入門知識

uva 10817 狀態壓縮DP

題意：

有S個課程要教，

學校本來有m個教師給出工資和所教課程編號（在職教師不能辭退）

來應聘的有n個教師給出工資和所教課程編號

問保證每個課程都有兩個老師可以教的前提下，最少發多少工資

思路：

水題；

總共最多只有8個課程，狀態壓縮

d[i][s1][s2] 表示當前狀態下，有一個老師教的課程是s1，有兩個或兩個人以上教的課程是s2

轉移就是當前教師選或不選，對應的轉移到下一個（i+1個）教師的決策即可。

code：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define mod 1000000007
typedef pair pii;
typedef long long LL;
//------------------------------
const int maxn = 125;
const int maxs = (1<<8);

int S,m,n;
int cost[maxn], s[maxn];

void init(){
    string line;
    int tmp;
    for(int i = 0; i < m+n; i++){
        getline(cin, line);
        stringstream ss(line);
        ss >> cost[i];
        s[i] = 0;
        while(ss >> tmp) s[i] |= (1 << (tmp-1));
    }
}
int d[maxn][maxs][maxs];
int dfs(int i, int s0, int s1, int s2){

    if(i == m + n) return s2 == (1<= 0) return ans;

    ans = INF;
    if(i >= m) ans = dfs(i+1, s0, s1, s2);

    int m0 = s[i] & s0, m1 = s[i] & s1;
    s0 ^= m0;
    s1 = (s1 ^ m1) | m0;
    s2 |= m1;
    ans = min(ans, cost[i] + dfs(i+1, s0, s1, s2));
    return ans;
}
void solve(){
    memset(d, -1, sizeof(d));
    int ans = dfs(0,(1<

一開始沒有用 
getlin(cin, line);
stringstream ss(line);
ss >> cost[i];
while(ss>>tmp){
}
這種方式來處理，而是采取了讀入到換行符的方式；
現在通過這道題目學習了一種新的處理方式。很好
 
code2：
 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define mod 1000000007
typedef pair pii;
typedef long long LL;
//------------------------------
const int maxn = 125;
const int maxs = (1<<8);

int S,m,n;
int cost[maxn], s[maxn];

void init(){
    int tmp;
    char ch;
    for(int i = 0; i < m+n; i++){
        scanf("%d",&tmp);
        cost[i] = tmp;
        s[i] = 0;
        while(1){
            scanf("%c",&ch);
            if(ch == '\n') break;
            if(isdigit(ch)){
                tmp = ch - '0';
                s[i] |= (1<<(tmp-1));
            }
        }
    }
}
int d[maxn][maxs][maxs];
int dfs(int i, int s0, int s1, int s2){

    if(i == m + n) return s2 == (1<= 0) return ans;

    ans = INF;
    if(i >= m) ans = dfs(i+1, s0, s1, s2);

    int m0 = s[i] & s0, m1 = s[i] & s1;
    s0 ^= m0;
    s1 = (s1 ^ m1) | m0;
    s2 |= m1;
    ans = min(ans, cost[i] + dfs(i+1, s0, s1, s2));
    return ans;
}
void solve(){
    memset(d, -1, sizeof(d));
    int ans = dfs(0,(1<maxs定義太大會超時