Codeforces #174 Div1. C. Coin Troubles

なかなか面白い問題だったC。
http://codeforces.com/contest/283/problem/C

問題

A[i]の価値を持つN種類のコインが与えられる。
各コインを何枚か用いて総計価値をTにする組み合わせ数を求めよ。
ただし、条件としていくつかの数p,qが与えられ、p番目のコインがq番目のコインより多いとする。
またすべてのp同士は一致せず、すべてのqは一致しない。

問題

まずコインの枚数の大小がループする場合は条件を満たせないので組み合わせ数は0。
それ以外の場合、p同士およびq同士は一致しないことから、各コイン枚数の大小関係は１列に表せる。
例えばi番目のコイン枚数をC[i]とするとき、C[a]

int N,Q,T;
int A[400];
int GT[400],LT[400];
ll DP[2][100002];
ll mo=1000000007;

int proc_loop() {
	int vis[400];
	int x;
	ZERO(vis);
	FOR(x,N) if(GT[x]==-1 && LT[x]==-1) vis[x]=1;
	FOR(x,N) if(LT[x]==-1 && GT[x]>=0) {
		int y=x;
		while(1) {
			vis[y]=1;
			if(GT[y]<0) break;
			T-=A[y];
			if(T<0) return 1;
			if(vis[GT[y]]==-1) return 1;
			A[GT[y]]+=A[y];
			y=GT[y];
		}
	}
	FOR(x,N) if(vis[x]==0) return 1;
	return 0;
	

}
void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	
	GET3(&N,&Q,&T);
	FOR(i,N) {
		A[i]=GETi();
		GT[i]=LT[i]=-1;
	}
	FOR(i,Q) {
		j=GETi()-1;
		k=GETi()-1;
		GT[j]=k;
		LT[k]=j;
	}
	
	if(proc_loop()) {
		_P("0\n");
		return;
	}
	
	DP[0][T]=1;
	FOR(i,N) {
		int cur=i%2;
		int tar=1-cur;
		ZERO(DP[tar]);
		for(j=T;j>=0;j--) {
			// add no A[i]
			DP[tar][j]=DP[cur][j];
			// add one A[i];
			if(j+A[i]<=T) DP[tar][j]=(DP[tar][j]+DP[tar][j+A[i]])%mo;
		}
	}
	_P("%lld\n",DP[N%2][0]);
	return;
}

まとめ

A[a]=A[a]+A[b]+A[c]+A[d]と置き換えるっていうアイデアが素晴らしいと思った。
今後こういう大小関係の制約がついた問題にであった場合、これを使うことを考えよう。