さてDiv1 Medium。本番に解き切れなかったのが残念。
http://community.topcoder.com/stat?c=problem_statement&pm=12534
問題
Nマスに狼を配置するのは、先のDiv2 Hardとおなじ。
Div2 Hardでは、[L,R]内に狼が1匹以上いることが必要だったが、こちらでは[L,R]内に狼が2匹以内でなければならない点が異なる。
解法
Div2 HardではマスXに対し1匹以上狼がいないといけない右限A[X]を求めたが、今度は2匹以下しか狼を置けない右限B[X]を先に求めておく。
次に、Div2 Hardでは各マスPの最寄の狼QについてDPしたが、今度はPの最寄の2匹の狼Q1,Q2に対してDPをすればよい。
Div2 HardはO(N^2)だったが、こちらは最寄の2匹の狼の位置でループを回すのでO(N^3)。
ll mo=1000000007; class WolfInZooDivOne { public: string concatvec(vector <string> expr) { return accumulate(expr.begin(),expr.end(),string("")); } vector<int> split_int(const string &str, char delim){ vector<int> res; size_t current = 0, found; while((found = str.find_first_of(delim, current)) != string::npos){ string s = string(str, current, found - current); res.push_back(atoi(s.c_str())); current = found + 1; } string s = string(str, current, str.size() - current); res.push_back(atoi(s.c_str())); return res; } int count(int N, vector <string> L, vector <string> R) { int i,x,y,z; int inval[301]; vector<int> LI=split_int(concatvec(L),' '); vector<int> RI=split_int(concatvec(R),' '); int MR[301]; FOR(x,N) MR[x]=-1; FOR(x,LI.size()) MR[LI[x]]=max(MR[LI[x]],RI[x]); FOR(x,N) FOR(y,x) if(MR[y]>=x) MR[x]=max(MR[x],MR[y]); ll DP[2][301][301]; ZERO(DP); DP[0][N][N]=1; int cur=0; for(x=N-1;x>=0;x--) { int tar=1-cur; ZERO(DP[tar]); for(y=x+1;y<=N;y++) { for(z=y;z<=N;z++) { // not put DP[tar][y][z] = (DP[tar][y][z] + DP[cur][y][z]) % mo; if(MR[x]<z || z==N) { // put DP[tar][x][y] = (DP[tar][x][y] + DP[cur][y][z]) % mo; } } } cur=1^cur; } ll res=0; FOR(x,N+1) FOR(y,N+1) res=(res+DP[cur][x][y])%mo; return (int)res; } };
まとめ
なんか似た問題見たな…と思ったらCF164 Div2 Dだな。
こういう数の条件が1とか2とか妙に小さい場合、その分の値を覚えてDPすることを考慮しよう。
下手にSRM576 Div1Mediumが頭に浮かんだおかげで、連結成分をどうこうするのかな?とか考えてしまってタイムロスしてしまった。