设为首页 加入收藏

TOP

bnu 12639 Cards （dp求期望）(一)
2015-07-20 17:52:22 来源: 作者: 【大 中 小】 浏览:5次
Tags：bnu 12639 Cards 期望

bnu 12639 Cards

dp求期望

区分 全局最优选择 和 当前最优选择。

本题是当前最优选择。

状态表示:

double dp[16][16][16][16][5][5];
bool vis[16][16][16][16][5][5];

状态下参数：

vector up, vector tmp。

so,记忆化搜索 + 回溯


//#pragma warning (disable: 4786)
//#pragma comment (linker, "/STACK:16777216")
//HEAD
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; //LOOP #define FE(i, a, b) for(int i = (a); i <= (b); ++i) #define FD(i, b, a) for(int i = (b); i>= (a); --i) #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(A,value) memset(A,value,sizeof(A)) #define CPY(a, b) memcpy(a, b, sizeof(a)) #define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++) //INPUT #define RI(n) scanf("%d", &n) #define RII(n, m) scanf("%d%d", &n, &m) #define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k) #define RS(s) scanf("%s", s) //OUTPUT #define WI(n) printf("%d\n", n) #define WS(s) printf("%s\n", s) typedef long long LL; const int INF = 1000000007; const double eps = 1e-10; const int MAXN = 1010; vector
               
                 goal; double dp[16][16][16][16][5][5]; bool vis[16][16][16][16][5][5]; inline bool check(vector
                
                  &tmp) { for (int i = 0; i < 4; i++) if (goal[i] > tmp[i]) return false; return true; } double dfs(vector
                 
                   &tmp, vector
                  
                    &up) { if (check(tmp)) return 0.0; if (vis[tmp[0]][tmp[1]][tmp[2]][tmp[3]][tmp[4]][tmp[5]]) return dp[tmp[0]][tmp[1]][tmp[2]][tmp[3]][tmp[4]][tmp[5]]; vis[tmp[0]][tmp[1]][tmp[2]][tmp[3]][tmp[4]][tmp[5]] = true; double ret = 0; int tot = 0; REP(i, 4) tot += tmp[i]; tot = 54 - tot; REP(i, 4) { if (up[i] > tmp[i]) { tmp[i]++; ret += (up[i] - tmp[i] + 1.0) / tot * dfs(tmp, up); tmp[i]--; } } if (up[4]) { double retmin = 100; REP(i, 4) { tmp[i]++; up[i]++; up[4]--; tmp[4] = i + 1; retmin = min(retmin, 1.0 / tot * dfs(tmp, up)); tmp[i]--; up[i]--; up[4]++; tmp[4] = 0; } ret += retmin; } if (up[5]) { double retmin = 100; REP(i, 4) { tmp[i]++; up[i]++; up[5]--; tmp[5] = i + 1; retmin = min(retmin, 1.0 / tot * dfs(tmp, up)); tmp[i]--; up[i]--; up[5]++; tmp[5] = 0; } ret += retmin; } dp[tmp[0]][tmp[1]][tmp[2]][tmp[3]][tmp[4]][tmp[5]] = ++ret; return ret; } int main () { int T; int ncase = 1; RI(T); while (T--) { int xx = 0, tot = 0; goal.clear(); REP(i, 4) { int x; RI(x); goal.push_back(x); if (x > 13) xx += x - 13; tot += x; } double ans; if (tot > 54 || xx > 2) { ans = -1.000; } else { memset(vis, 0, sizeof(vis)); vector
                   
                     tmp, up; REP(i, 6) tmp.push_back(0); REP(i, 4) up.push_back(13); REP(i, 2) up.push_back(1); ans = dfs(tmp, up); if (ans < 0) ans = 0.000; } printf("Case %d: %.3lf\n", ncase++, ans); } return 0; }

稍微有点不同的写法 

//#pragma warning (disable: 4786)
//#pragma comment (linker, "/STACK:16777216")
//HEAD
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; //LOOP #define FE(i, a, b) for(int i = (a); i <= (b); ++i) #define FD(i, b, a) for(int i = (b); i>= (a); --i) #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(A,value) memset(A,value,sizeof(A)) #define CPY(a, b) memcpy(a, b, sizeof(a)) #define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++) //INPUT #define RI(n) scanf("%d", &n) #define RII(n, m) scanf("%d%d", &n, &m) #define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k) #define RS(s) scanf("%s", s) //OUTPUT #define WI(n) printf("%d\n", n) #define WS(s) printf("%s\n", s) typedef long long LL; const int INF = 1000000007; const double eps = 1e-10; const int MAXN = 1010; vector
               
                 goal; double dp[14][14][14][14][5][5]; bool vis[14][14][14][14][5][5]; inline bool check(vector
                
                  &tmp) { int xx = tmp[4], yy = tmp[5]; if (xx) tmp[xx - 1]++; if (yy) tmp[yy - 1]++; bool ret = true; for (int i = 0; i < 4; i++) if (goal[i] > tmp[i]) ret = false; if (xx) tmp[xx - 1]--; if (yy) tmp[yy - 1]--; return ret; } double dfs(vector
                 
                   &tmp) { if (check(tmp)) return 0.0; if (vis[tmp[0]][tmp[1]][tmp[2]][tmp[3]][tmp[4]][tmp[5]]) return dp[tmp[0]][tmp[1]][tmp[2]][tmp[3]][tmp[4]][tmp[5]]; vis[tmp[0]][tmp[1]][tmp[2]][tmp[3]][tmp[4]][tmp[5]] = true; double ret = 0; int tot = 0; REP(i, 4) tot += tmp[i]; int xx = tmp[4], yy = tmp[5]; if (xx) tot++; if (yy) tot++; tot = 54 - tot; REP(i, 4) { if (13 > tmp[i]) { tmp[i]++; ret += (13 - tmp[i] + 1.0) / tot * dfs(tmp); tmp[i]--; } } if (!xx) { double retmin = 100; REP(i, 4) { tmp[4] = i + 1; retmin = min(retmin, 1.0 / tot * dfs(tmp)); tmp[4] = 0; } ret += retmin; } if (!yy) { double retmin = 100; REP(i, 4) { tmp[5] = i + 1; retmin = min(retmin, 1.0 / tot * dfs(tmp)); tmp[5] = 0; } ret += retmin; } dp[tmp[0]][tmp[1]][tmp[2]][tmp[3]][tmp[4]][tmp[5]] = ++ret; return ret; } int main () { int T; int ncase = 1; RI(T); while (T--) { int xx = 0, tot = 0; goal.clear(); REP(i, 4) { int x;
首页 上一页 1 2 下一页 尾页 1/2/2
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：poj1185炮兵布阵结题报告--初步了.. 下一篇：uva 1549 - Lattice Point(暴力)

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: