tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 2587: Elevator Hall Number

左からi桁決めたときに次に挙げるもののうちどれにマッチするかの集合がどれか、でbitDP。

  • k個の整数が終了した
  • k個目の整数の10の位まで終了した。1の位で可能なパターンは某(場合によるが3種類くらいある)

押し込むと最大18bit。

遷移もやはり場合わけが必要。いくつか漏らしやすい。

#include<stdio.h>
#include<algorithm>
using namespace std;
long long dp[13][1<<18];
int L[10];
int R[10];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++){
			scanf("%d%d",L+i,R+i);
		}
		for(int i=0;i<13;i++)for(int j=0;j<(1<<(a*3));j++)dp[i][j]=0;
		for(int i=1;i<10;i++){
			int to=0;
			if(L[0]<=i&&i<=R[0])to+=1;
			if((L[0]/10<=i&&i<R[0]/10)||(L[0]/10==R[0]/10&&i==L[0]/10))to+=2;
			if(L[0]/10<i&&i<=R[0]/10)to+=4;
			dp[1][to]++;
		}
		for(int i=1;i<a*2;i++){
			for(int j=0;j<(1<<(a*3));j++){
				if(!dp[i][j])continue;
				if(!j)continue;
			//	printf("%d %d: %lld\n",i,j,dp[i][j]);
				for(int k=0;k<10;k++){
					int to=0;
					for(int l=0;l<a*3;l++){
						if(!(j&(1<<l)))continue;
						if(l==a*3-3)continue;
						if(l%3==0){
							if(k==0)continue;
							if(L[l/3+1]<=k&&k<=R[l/3+1])to|=(1<<(l+3));
							if((L[l/3+1]/10<=k&&k<R[l/3+1]/10)||(L[l/3+1]/10==R[l/3+1]/10&&k==L[l/3+1]/10))to|=(1<<(l+4));
							if(L[l/3+1]/10<k&&k<=R[l/3+1]/10)to|=(1<<(l+5));
						}else if(l%3==1&&(j&(1<<(l+1)))){
							to|=(1<<(l-1));
						}else if(l%3==1){
							if(L[l/3]/10==R[l/3]/10){
								if(L[l/3]%10<=k&&k<=R[l/3]%10)to|=(1<<(l-1));
							}else if(L[l/3]%10<=k)to|=(1<<(l-1));
						}else{
							if(k<=R[l/3]%10)to|=(1<<(l-2));
						}
					}
					if(to)dp[i+1][to]+=dp[i][j];
				}
			}
		}
		long long ret=0;
		for(int i=0;i<=a*2;i++){
			for(int j=0;j<(1<<(a*3));j++){
				if(j&(1<<(a*3-3)))ret+=dp[i][j];
			}
		}
		printf("%lld\n",ret);
	}
}