uva 10817 状态压缩DP - c++编程基础

TOP

uva 10817 状态压缩DP

2015-11-21 01:02:19 来源: 作者: 【大中小】浏览:1次

Tags：uva 10817 状态压缩

题意：

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


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：c++学习第一课--输入/输出	下一篇：Valid Palindrome -- leetcode

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: