TopCoder SRM 501 Div1 Medium FoxAverageSequence

久々にDiv2 Hardと共通の問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11340

問題

0～40の整数で構成される数列A[i]が与えられる。
ただし、一部の数値は未定であり、そこは0～40の任意の整数を埋めてよい。

以下の条件を満たす数列Aは何通りあるか答えよ。

• A[i]はそこまでの数値の平均以下である。すなわちA[i] <= (A[0]+A[1]+..+A[i-1])/iである。
• 連続する3要素が真に単調減少であってはならない。すなわちA[i] > A[i+1] > A[i+2]となるiがあってはならない。

解法

状態として[そこまでのA[i]の総和][直前のA[i-1]の値][真に単調減少を何回連続させたか]を持ってDPするだけ。
要素数N、数値の最大値Pとすると、全体でO(N*NP*P*P)=O(N^2*P^3)で解ける。
N<=40、P<=40なのでなんとか解ける。

ll dpdp[2][2001][41][2];
ll mo=1000000007;

class FoxAverageSequence {
	public:
	int theCount(vector <int> seq) {
		int N=seq.size();
		int i,x,y,z;
		
		ZERO(dpdp);
		
		FOR(y,41) {
			if(seq[0]!=-1 && seq[0]!=y) continue;
			dpdp[1][y][y][0]=1;
		}
		
		for(i=1;i<N;i++) {
			int cur=i%2,tar=cur^1;
			ZERO(dpdp[tar]);
			FOR(x,1601) {
				FOR(y,41) {
					if(seq[i]!=-1 && seq[i]!=y) continue;
					if(i*y>x || x+y>1600) break;
					FOR(z,41) {
						if(seq[i-1]!=-1 && seq[i-1]!=z) continue;
						if(dpdp[cur][x][z][0]==0 && dpdp[cur][x][z][1]==0) continue;
						if(y<z) dpdp[tar][x+y][y][1] = (dpdp[tar][x+y][y][1] + dpdp[cur][x][z][0]) % mo;
						else dpdp[tar][x+y][y][0] = (dpdp[tar][x+y][y][0] + dpdp[cur][x][z][0] + dpdp[cur][x][z][1]) % mo;
					}
				}
			}
			
			
		}
		
		ll ret=0;
		FOR(i,2001) FOR(x,41) FOR(y,2) ret += dpdp[N%2][i][x][y];
		return ret % mo;
	}
}

まとめ

Div1 Mediumにしては面倒なだけでヒネリのない問題。