「AOJ1500~1509」の編集履歴(バックアップ)一覧に戻る

AOJ1500~1509 - (2013/01/12 (土) 18:02:51) のソース

*問い1500 ID
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1500
条件を満たすIDが幾通りあるか答える問題。

解法
-*の数も少なくメモ化で一発です。


 #include<stdio.h>
 #include<string.h>
 char id[100001];
 int memo[100001][10];
 int main(){
 	
 	int n,m,a;
 	int base2[10]={0,2,4,6,8,1,3,5,7,9};
 	bool oks[10]={0,0,0,0,0,0,0,0,0,0};
 	scanf("%d %s",&n,id);
 	scanf("%d",&m);
	for(int i=0;i<m;i++){
  		scanf("%d",&a);
		oks[a]=true;
  	}
 
 	memset(memo,0,sizeof(memo));
 	memo[0][0]=1;
 	for(int i=1;i<=n;i++){
 		char c=id[n-i];
 		if(c=='*'){
 			for(int j=0;j<=9;j++){
 				for(int k=0;k<=9;k++){
 					if(oks[k]==true){
 						if(i%2==0)memo[i][(j+base2[k])%10]+=memo[i-1][j];
 						else memo[i][(j+k)%10]+=memo[i-1][j];
 					}
 				}
 			}
 		}else{
 			for(int j=0;j<=9;j++){
 				if(i%2==0)memo[i][(j+base2[c-'0'])%10]+=memo[i-1][j];
 				else memo[i][(j+(c-'0'))%10]+=memo[i-1][j];
 			}
 		}
  	}
  	printf("%d\n",memo[n][0]);
 }