今天看啥
热点:

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定义太大会超时

 

www.bkjia.comtruehttp://www.bkjia.com/cjjc/999616.htmlTechArticleuva 10817 状态压缩DP 题意: 有S个课程要教, 学校本来有m个教师 给出工资和所教课程编号 (在职教师不能辞退) 来应聘的有n个教师 给出工...

相关文章

相关搜索: 状态

帮客评论

视觉看点