Android教程網 >> Android技術 >> 關於Android編程 >> Codeforces Round #216 (Div. 2) D. Valera and Fools

Codeforces Round #216 (Div. 2) D. Valera and Fools

編輯：關於Android編程

注意題意：所有fools都向編號最小的fool開槍；但每個fool都不會笨到想自己開槍，所以編號最小的fool向編號次小的fool開槍；

所以只需記錄編號最小的兩位成員即可代表一種狀態；當然當只剩一個fool時，次小編號是不存在的出界元素。

編號最小的兩個fools只有四種狀態：a活b活，a死b死，a活b死，a死b活；注意狀態轉移條件。

記憶化搜索即可（算法上依然是搜索的流程，但是搜索到的一些解用動態規劃的那種思想和模式作一些保存。）

代碼及注釋如下：

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#define  N 3010 
using namespace std;
int p[N],maxp[N];  
int vis[N][N];   //訪問標記 
int n,k,cnt=0; 
void dfs(int a,int b,int t){  //a最小,b次小,t記錄開槍次數 
  if(vis[a][b])  return;
  vis[a][b]=1;
  cnt++;
  if(t==k||b>=n)  return;
  if(p[a]){  //若a的概率不為0,則b就可能killed     
    if(maxp[b])  dfs(b+1,b+2,t+1);    //a,b都killed
    if(maxp[b]!=100)  dfs(a,b+1,t+1);  //b killed 
  }
  //若a的概率不為100,則b就可能living;若b~n的最大概率不為0,則a就可能killed 
  if(p[a]!=100 && maxp[b]!=0)  dfs(b,b+1,t+1);
}
int main()
{
  int i,j;
  while(scanf(%d %d,&n,&k)!=EOF){
    memset(maxp,0,sizeof(maxp));
    memset(vis,0,sizeof(vis));
    cnt=0;
    for(i=0;i=0;i--) maxp[i]=max(maxp[i+1],p[i]);  //記錄從i至n的最大概率值 
    dfs(0,1,0);
    printf(%d
,cnt);
  }
  return 0;
}