HDU 4371 AliceBob之生成數列直到大於n或者小於等於S(i-2)-思維-（由已知條件推最優步驟）

HDU 4371 AliceBob之生成數列直到大於n或者小於等於S(i-2)-思維-（由已知條件推最優步驟）

題意：已知n、d1、d2....dm，Alice先生成一個數S1=0，Bob再生成一個數S2=S1+dk，之後他們生成的數遵循這樣的條件：Si=S(i-1)+dk，或者Si=S(i-1)-dk，其中1<=k<=m，S(i-2)

分析：

既然想不出什麼直接搜索之類的方法，那麼一定就是找規律了。這題我們來推一下他的條件得到每個人每一步的最利於自己的做法。

考慮三個數：S(i-2),S(i-1),Si，假設當前步驟是生成Si，那麼必須滿足的條件是S(i-2)

1.Si=S(i-1)+dk

那麼對於S(i-1)這個人（設為A）來說，他想讓Si（設為B）輸，所以A在生成S(i-1)的時候肯定是想構造一個數S(i-1)，讓B無論怎麼選擇dk都不能由S(i-1)生成合法的Si。

不合法的Si也就是Si<=S(i-2)並且Si>n，也就是說即使選擇最小的dmin也不能滿足S(i-1)-dmin>S(i-2)或者S(i-1)+dmin<=n，又因為S(i-1)=S(i-2)+dk，帶入得：

S(i-2)+dk-dmin<=S(i-2) 且 S(i-2)+dk+dmin>n，滿足這兩個條件的dk只能是dmin，所以A在生成S(i-1)的時候為了使B輸，他會選擇+dmin

2.Si=S(i-1)-dk

推理方法同理，你會發現這個不能在生成自己的時候陷害別人，所以這個不是最利於自己的做法。

綜上，每個人每一步都會選擇最利於自己的做法是+dmin，之後就模擬一遍，然後誰先>n就誰輸。

博弈問題一般解法：根據條件推出每人最利於自己的做法然後：1.模擬一遍得出結果；2.根據數據特征如奇偶性直接判斷出結果

代碼：

#include
#include
#include
#include
#include
#define INF 1000000007
using namespace std;
int t,n,m;
int d;
int main()
{
     scanf(%d,&t);
	 for(int cas=1;cas<=t;cas++){
	 	scanf(%d%d,&n,&m);
	 	int mi=INF;
	 	for(int i=0;in) ok=1;
	    else{
		    	while(1){
			    	int tmp=a;
			    	a=b+mi;
			    	b=a+mi;
			    	if(a>n){
			    		ok=0;break;
			    	}
			    	if(b>n){
			    		ok=1;break;
		    	    }
		        }
	    }	    
	    printf(Case #%d: ,cas);
	    if(ok) printf(Alice
);
	    else printf(Bob
);
	 }	
}