博弈dp.docx

1、博弈dp博弈DP Jiangnan Universit Liyang 2014/10/24题意：有N个数，有一个区间A,B,第一个人先取一个数，必须在区间内，后一次取必须比第一个数大，而且差值在区间内。问最后两个人取的数的和的差值最大为多少。const int maxn = 10008 ;const int inf = 1000000000 ;int xmaxn ;int a , b , n ;int dpmaxn ;int dfs(int id) if(dpid != -inf) return dpid ; int t = inf ; for(int i = id + 1 ; i = a &

2、 xi - xid t ; while(t-) cinnab ; for(i = 1 ; i = n ; i+) scanf(%d , &xi) ; sort(x+1 , x+1+n) ; for(i = 1 ; i = n ; i+) dpi = - inf ; ans = -inf ; for(i = 1 ; i = a & xi r & L R) return 0 ; if(dplrLR != -1) return dplrLR ; dplrLR = 0 ; int sum = sar - sal-1 + sbR - sbL-1 ; if(l = r) dplrLR = max(sum

3、- dfs(l+1 , r , L , R) , dplrLR) ; dplrLR = max(sum - dfs(l , r-1 , L , R) , dplrLR) ; if(L t ; while(t-) cinn ; sa0 = 0 ; for(i = 1 ; i = n ; i+) scanf(%d , &ai) ; sai = sai-1 + ai ; sb0 = 0 ; for(i = 1 ; i = n ; i+) scanf(%d , &bi) ; sbi = sbi-1 + bi ; memset(dp , -1 , sizeof(dp) ; cout dfs(1 , n

4、, 1 , n) endl ; return 0 ;两个公司从教育部轮流申请资金，如果库中钱充足的话那么就会拨给这个公司，如果一旦库中没有钱那么停止，如果申请的钱多余库中的那么教育部长会 把手中的m元钱给他之后申请结束，开始库中有n元钱，每个公司每次申请资金的范围是1 , k，问先手的公司最多能得到多少钱，在得到最多钱的情况下 能让对手得到最少的钱数。题解：开始是博弈的想法，枚举每个人决策的平衡态，莫名其妙的过了，队友搞了dp，找到一组反例证明我的博弈想法是有错误的，dp应该是正解。 dp i 0 代表的是当前剩余 i 元钱先手申请到的最多的钱，dp i 1 代表剩余 i 元钱先手得到的最多钱

5、时对手得到的最少的钱，const int maxn = 22 ;int n , m , k ;bool vis100022 ;typedef pair pt ;pt dp100022 ;pt dfs(int state , int t) if(visstatet) return dpstatet ; visstatet = 1 ; if(state = 0) return dpstatet = pt(0 , 0) ; pt now(0 , 0) ; for(int i = 1 ; i = i) pt nx = dfs(state-i , t1) ; if(i + nx.second now.f

6、irst) now.first = i + nx.second ; now.second = nx.first ; else if(i + nx.second = now.first) now.second = min(now.second , nx.first) ; else if(now.first nmk) memset(vis , 0 , sizeof(vis) ; pt t = dfs(n , 0) ; printf(%d %dn , t.first , t.second) ; return 0 ;给定n个数字，A和B可以从这串数字的两端任意选数字，一次只能从一端选取（若干个）。并且

7、A B都尽力使自己选择的结果为最大的，可以理解成A B每一步走的都是最优的。如果A先选择，则A B差值最大是多少。const int maxn = 108 ;const int inf = 1000000000 ;int amaxn , samaxn ;int n ;int dpmaxnmaxn ;bool vismaxnmaxn ;int sum(int l , int r) int t = 0 ; if(l r) return 0 ; if(vislr) return dplr ; int s = sum(l , r) ; int t = -inf ; for(int i = l ; i

8、= l ; i-) t = max(t , sum(i , r) - dfs(l , i-1) ; vislr = 1 ; if(t = -inf) return dplr = 0 ; return dplr = t ;int main() int i ; while(cinn & n) sa0 = 0 ; for(i = 1 ; i = n ; i+) scanf(%d , &ai) ; sai = sai-1 + ai ; memset(vis , 0 , sizeof(vis) ; cout dfs(1 , n) endl ; return 0 ;题目大意：有B个盒子里面放有G种颜色的宝

9、石，两个人轮流选一个盒子将其中的宝石取出来放到一个锅里，然后其中没有S个相同颜色的宝石，它们就会聚合在一起变成一个魔法石（可能产生多个魔法石且锅里有可能有剩余的宝石），然后本轮的得分就是产生的魔法石的数量，且如果本轮某个人拿到了魔法石的话，那么下一轮他还可以继续选择盒子放入宝石，知道他在某一轮没有拿到魔法石，现在问两个人都采用最优策略的情况下，到最后先拿的那个人的得分与后拿的人的得分的差是多少。const int maxn = 22 ;int b , g , s ;vector bgmaxn ;int score1maxn ;int summaxn ;bool vis1maxn ;int dp

10、1maxn ;int dfs(int state) if(visstate) return dpstate ; visstate = 1 ; for(int i = 0 ; i b ; i+) if(state & (1i) int t = scorestate (1 0) dpstate = max(dpstate , dfs(state (1 i) + t) ; else dpstate = max(dpstate , score0 - scorestate - dfs(state (1gbs) if(g = 0 & b = 0 & s = 0) break ; for(i = 0 ; i

11、 b ; i+) bgi.clear() ; for(i = 0 ; i b ; i+) scanf(%d , &n) ; while(n-) scanf(%d , &x) ; bgi.push_back(x) ; n = 1b; for(i = 0 ; i n ; i+) scorei = 0 ; memset(sum , 0 , sizeof(sum) ; for(j = 0 ; j b ; j+) if(i & (1j) = 0) for(k = 0 ; k bgj.size() ; k+) sumbgjk+ ; for(j = 1 ; j = g ; j+) scorei += sum

12、j / s ; memset(vis , 0 , sizeof(vis) ; memset(dp , 0 , sizeof(dp) ; cout 2 * dfs(n-1) - score0 endl ; return 0 ;题意：20之内的数字，每次可以选一个数字，然后它的倍数，还有其他已选数的倍数组合的数都不能再选，谁先不能选数谁就输了，问赢的方法const int N = 1050005;int t, n, w, start, dpN, ans25, an;int getnext(int state, int x) for (int i = x; i = 20; i += x) if (s

13、tate&(1(i - 2) state = (1(i - 2); for (int i = 2; i = 20; i+) if (state&(1= 2; j += x) if (!(state&(1(i - j - 2) state = (1(i - 2); break; return state;int dfs(int state) if (dpstate != -1) return dpstate; if (state = 0) return dpstate = 0; for (int i = 2; i = 20; i+) if (state&(1(i - 2) if (dfs(get

14、next(state, i) = 0) return dpstate = 1; return dpstate = 0;int main() int cas = 0; memset(dp, -1, sizeof(dp); scanf(%d, &t); while (t-) start = 0; an = 0; scanf(%d, &n); for (int i = 0; i n; i+) scanf(%d, &w); start |= (1(w - 2); for (int i = 2; i = 20; i+) if (start&(1(i - 2) if (dfs(getnext(start,

15、 i) = 0) ansan+ = i; printf(Scenario #%d:n, +cas); if (an) printf(The winning moves are:); for (int i = 0; i an; i+) printf( %d, ansi); printf(.n); else printf(There is no winning move.n); printf(n); return 0;给你2n个人，两方各n个人，交叉坐，每个人可以取的石子有一个最大限制，总共有S颗石子，哪一方取了最后一颗石子就输了，问先取石子的这一方是否有必胜策略。const int maxn =

16、 113 + 5 ;bool vismaxn22 ;int n ;int a22 ;int dpmaxn22 ;int dfs(int sum , int id) if(vissumid) return dpsumid ; vissumid = 1 ; if(sum = 0) return dpsumid = 1 ; for(int i = 1 ; i = aid & i n & n) cins ; for(i = 0 ; i 2*n ; i+) scanf(%d , &ai) ; memset(vis , 0 , sizeof(vis) ; cout dfs(s , 0) n & n) fo

17、r(i = 1 ; i = n ; i+) scanf(%lld , &ai) ; dp1i1 = ai ; dp1i0 = 0 ; k = 0 ; for(int len = 2 ; len = n ; len+) for(i = 1 ; i+len-1 = n ; i+) if(len % 2 = 0) dpki0 = max(ai + dpk1i+10 , ai+len-1 + dpk1i0) ; dpki1 = min(dpk1i1 , dpk1i+11) ; else dpki1 = max(ai + dpk1i+11 , ai+len-1 + dpk1i1) ; dpki0 = m

18、in(dpk1i0 , dpk1i+10) ; k = 1 ; cout dpk110 endl ; return 0 ;三堆石头，每次从一堆中取走若干，或者从两堆中取走相同的数量 ，最后取的人胜。bool dpmaxnmaxnmaxn ;void DP() memset(dp , 0 , sizeof(dp) ; int i , j , k , r ; for(i = 0 ; i = 300 ; i+) for(j = 0 ; j = 300 ; j+) for(k = 0 ; k = 300 ; k+) if(dpijk) continue ; for(r = 1 ; i + r = 30

19、0 ; r+) dpi+rjk = 1 ; for(r = 1 ; j + r = 300 ; r+) dpij+rk = 1 ; for(r = 1 ; k + r = 300 ; r+) dpijk+r = 1 ; for(r = 1 ; i+ r = 300 & j + r = 300 ; r+) dpi+rj+rk = 1 ; for(r = 1 ; i + r = 300 & k + r = 300 ; r+) dpi+rjk+r = 1 ; for(r = 1 ; j + r = 300 & k + r abc) cout dpabc y = y ; this-m = m ; this-d = d ; int valid() / 2001) return 0 ; if(y 11) return 0 ; if(m = 11 & d 4) return 0 ; if(leap(y) & m =