(DP)Ivan the Fool and the Probability Theory---------- Codeforces Round #594 (Div. 2)
1976 ワード
https://codeforces.com/contest/1248/problem/C
問題:Nを1つ与える×Mサイズの格子図は、現在、各格子を白黒2色に染めることが要求されており、各格子はせいぜい4方向(上下左右)の1つの格子と同色であることが要求されており、どのような案があるかを尋ねている.
構想:最初の行または最初の列を決定すると、図全体の構造が決定されます.
1行目に同じ色の格子が2つ存在し、1行目の色が決定された場合、下の各行の構造が決定され、隣接する2つのブロックの前または後がどの色であるかにかかわらず、下の行の色は必ず上の行とは逆であり、単独で列から見ることができる.各列は白黒が交錯している(まず白黒の2つの状況を排除する)ので、まず1行の中に白黒が交錯している場合を排除しますか?例えば010101、次の行は101010、あるいは010101で、唯一確定できないので、まず彼を排除します
列から見ると、各列に同じ色の格子が2つ存在し、第1列の色が決定されると、各行の色は第1列の色によって決定され、(第1列に注意)、絵は、列から各行の色を決定し、各行が白黒であることを発見することができ、それはなぜ前に各行の白黒の間の2つの状況を排除しなければならないのかを説明している.
まとめると、1列目の要素が厳密な白黒の間であれば、各行が1列目の色で決まる(注意は1列目)、dp 1列の場合、1行目が厳密な白黒の間でなければ、後の数行が固定される
そこで、dp[i][0]を長さiの格子で色が白色のスキーム数、dp[i][1]を長さiの格子で色が黒色のスキーム数として書き始めることができる.
ではまず境界条件を考えてみましょう
1つの格子は、黒または白、すなわちdp[1][0]=1、dp[1][1]=1しかない.
2つの格子、dp[2][0]=2は、前の格子が黒でも白でもあるため、2つの案があり、同じdp[2][1]=2である
境界条件が確定すれば、dpで他のものを出すことができます.
最後にdp[i]=dp[i-1]+dp[i-2]を得る
何人かの大物のブログに感謝します
https://blog.csdn.net/weixin_42856843/article/details/102655689#commentsedit
https://blog.csdn.net/toohandsomeIeaseId/article/details/102668813#commentsedit
https://blog.csdn.net/qq_37656398/article/details/102660797
問題:Nを1つ与える×Mサイズの格子図は、現在、各格子を白黒2色に染めることが要求されており、各格子はせいぜい4方向(上下左右)の1つの格子と同色であることが要求されており、どのような案があるかを尋ねている.
構想:最初の行または最初の列を決定すると、図全体の構造が決定されます.
1行目に同じ色の格子が2つ存在し、1行目の色が決定された場合、下の各行の構造が決定され、隣接する2つのブロックの前または後がどの色であるかにかかわらず、下の行の色は必ず上の行とは逆であり、単独で列から見ることができる.各列は白黒が交錯している(まず白黒の2つの状況を排除する)ので、まず1行の中に白黒が交錯している場合を排除しますか?例えば010101、次の行は101010、あるいは010101で、唯一確定できないので、まず彼を排除します
列から見ると、各列に同じ色の格子が2つ存在し、第1列の色が決定されると、各行の色は第1列の色によって決定され、(第1列に注意)、絵は、列から各行の色を決定し、各行が白黒であることを発見することができ、それはなぜ前に各行の白黒の間の2つの状況を排除しなければならないのかを説明している.
まとめると、1列目の要素が厳密な白黒の間であれば、各行が1列目の色で決まる(注意は1列目)、dp 1列の場合、1行目が厳密な白黒の間でなければ、後の数行が固定される
そこで、dp[i][0]を長さiの格子で色が白色のスキーム数、dp[i][1]を長さiの格子で色が黒色のスキーム数として書き始めることができる.
ではまず境界条件を考えてみましょう
1つの格子は、黒または白、すなわちdp[1][0]=1、dp[1][1]=1しかない.
2つの格子、dp[2][0]=2は、前の格子が黒でも白でもあるため、2つの案があり、同じdp[2][1]=2である
境界条件が確定すれば、dpで他のものを出すことができます.
最後にdp[i]=dp[i-1]+dp[i-2]を得る
#include
using namespace std;
typedef long long ll;
inline int read(){
int X=0,w=0;char ch=0;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
/*------------------------------------------------------------------------*/
const int maxn=1e5+10;
const int mod=1e9+7;
int dp[maxn];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("a.txt","r",stdin);
//freopen("a.txt","w",stdout);
int n,m;
cin>>n>>m;
dp[1]=2;
dp[2]=4;
for(int i=3;i<=max(n,m);++i){
dp[i]=(dp[i-1]+dp[i-2])%mod;
}
cout< 何人かの大物のブログに感謝します
https://blog.csdn.net/weixin_42856843/article/details/102655689#commentsedit
https://blog.csdn.net/toohandsomeIeaseId/article/details/102668813#commentsedit
https://blog.csdn.net/qq_37656398/article/details/102660797