SRM 578 DIV1 Middle - WolfInZooDivOne （復習x）
問題
Ｎ個のセクションに区切られた道路を渡りたい。
ただし、各セクションには多くて１匹の狼がいるので注意して歩かなくてはいけない。
今回上記に加えて、狼の存在について追加の情報が与えられる。
複数のleft[i]、right[i]が与えられ、この区間中に最大で２匹の狼が存在する。
このとき、各セクションの狼の存在についてすべての場合の数を求める。
解き方
ｄｐで解けそうな問題なので、どのようにｄｐを設計するか。
現在の状態を考えた時に、最後に狼がいたセクションと現在いるセクションを考える。
この状態のすべての場合の数は、以下の２通りになる。
（１）現在のセクションに狼を追加せずに次のセクションに移る場合
（２）現在のセクションに狼を追加して次のセクションに移る場合
ただし（２）の場合は、与えられた条件の制約から次に移ることのできるセッションは限られる。
具体的には、前に狼がいたセクションと今回追加するセクションが両方含まれるセクションは
狼が２匹以上となりこれ以上狼は追加できないので、その次の場所から検索することになる。
あとは上記の条件をＤＦＳで実装すればよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int N,n,dp[305][305];
vector<int> s,t;
class WolfInZooDivOne {
public:
vector<int> parse(vector<string> str){
string s="";
FORE(i,0,str.size())s+=str[i];
stringstream out(s);
vector<int> vx;
for(int tmp;out>>tmp;)vx.push_back(tmp+1);
return vx;
}
int rec(int last,int pos){
if(pos>N)return 1;
if(dp[last][pos]!=-1)return dp[last][pos];
int ret=rec(last,pos+1);
int end=pos;
FORE(i,0,n)if(s[i]<=last&&pos<=t[i])end=max(end,t[i]);
ret=(ret+rec(pos,end+1))%1000000007;
return dp[last][pos]=ret;
}
int count(int N_, vector<string> L, vector<string> R) {
memset(dp,-1,sizeof(dp));
s.clear(),t.clear();
N=N_;
s=parse(L);
t=parse(R);
n=s.size();
return rec(0,1);
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int N,n,dp[305][305];
vector<int> s,t;
class WolfInZooDivOne {
public:
vector<int> parse(vector<string> str){
string s="";
FORE(i,0,str.size())s+=str[i];
stringstream out(s);
vector<int> vx;
for(int tmp;out>>tmp;)vx.push_back(tmp+1);
return vx;
}
int rec(int last,int pos){
if(pos>N)return 1;
if(dp[last][pos]!=-1)return dp[last][pos];
int ret=rec(last,pos+1);
int end=pos;
FORE(i,0,n)if(s[i]<=last&&pos<=t[i])end=max(end,t[i]);
ret=(ret+rec(pos,end+1))%1000000007;
return dp[last][pos]=ret;
}
int count(int N_, vector<string> L, vector<string> R) {
memset(dp,-1,sizeof(dp));
s.clear(),t.clear();
N=N_;
s=parse(L);
t=parse(R);
n=s.size();
return rec(0,1);
}
};
