Хорошие игровые последовательности
Учитывая две игры A и B, и есть ограничения, что A можно играть в нечетные минуты, а B можно играть только в четные минуты. Как Play A на 1-й секунде, а затем на 3-й секунде, аналогично для B.
Теперь хорошая последовательность определяется как:
(1) Если в игры играют в соответствии с их правилом, т. Е. А будет играть в нечетные минуты, а В - в четные минуты.
(2) A и B не воспроизводятся поочередно во всей последовательности.
Например,
AXAXA: X обозначает отсутствие игры в эту минуту, хорошая последовательность.
ABXXXB: Хорошая последовательность, потому что оба играются в соответствии с правилом, а сначала воспроизводится A, затем B, а затем снова B.
XXXX: Хорошая последовательность.
ABXXAB: не очень хорошая последовательность.
Учитывая общее количество минут, до которых игра ведется, рассчитайте общее количество хороших последовательностей. Так как число может быть довольно большим, предоставьте ответ по модулю 1000000007.
Я делаю это, создавая каждую строку и проверяя ее правильность. Это O(2^n). У меня есть ответы на меньшее количество n: 2, 3, 5, 9, 18, 38, 82, 177, 379, 803,.... n, начиная с 1.
Как мне сделать это через DP?
2 ответа
Этот код работает для вас, я добавил демо здесь. Пожалуйста, проверьте это
#include <iostream>
#include <cstdio>
using namespace std;
#define MOD 1000000007
int dp[100005][3][4]= {0};
int main() {
int n;
cin >> n;
dp[1][0][1] = 1;
dp[1][2][0] = 1;
for(int i=2; i<=n; i++){
if(i&1){
dp[i][2][0] = dp[i-1][2][0];
dp[i][0][1] = dp[i-1][2][0];
dp[i][2][1] = (dp[i-1][0][1] + dp[i-1][2][1]);
dp[i][1][3] = dp[i-1][1][3];
dp[i][2][2] = (dp[i-1][1][2] + dp[i-1][2][2])%MOD;
dp[i][0][3] = ((dp[i-1][1][2] + dp[i-1][2][2])%MOD + (dp[i-1][1][3] + dp[i-1][0][3])%MOD)%MOD;
}
else {
dp[i][2][0] = dp[i-1][2][0];
dp[i][1][2] = dp[i-1][2][0];
dp[i][2][1] = (dp[i-1][0][1] + dp[i-1][2][1]);
dp[i][1][3] = ((dp[i-1][0][1] + dp[i-1][2][1])%MOD + (dp[i-1][1][3] + dp[i-1][0][3])%MOD)%MOD;
dp[i][2][2] = (dp[i-1][1][2] + dp[i-1][2][2])%MOD;
dp[i][0][3] = dp[i-1][0][3];
}
// for(int j=0;j<=2;j++){
// for(int k=0;k<=3;k++){
// if(dp[i][j][k])
// printf("i=%d j=%d k=%d dp=%d\n",i,j,k,dp[i][j][k]);
// }
// }
}
int p = 1;
for(int i=1; i<=n; i++){
p = (p*2) % MOD;
}
p = (p - dp[n][0][3] - dp[n][1][3] )%MOD;
p = (p+MOD)%MOD;
cout << p << endl;
return 0;
}
Допустим, у нас есть государства
- x, xx, - при добавлении b это приводит к состоянию 2, когда a приводит к 3, когда x не меняет состояние
- xb, xbxbx, - когда x без изменений в состоянии, b без изменений в состоянии, когда a приводит к состоянию 5
- a, axa, - когда x без изменений в состоянии, когда a без изменений в состоянии, когда b приводит к состоянию 4
- ab, xxab, abx - x нет изменений в состоянии, для b оно переходит в состояние 2, следует пренебречь добавлением
- xba, xbax - x нет изменений в состоянии, для a оно меняется на 3, для b мы должны пренебречь добавлением b
Таким образом, вы решаете, переходя от небольшого диапазона (длина 1) к заданному диапазону и продолжая считать состояния, добавляя x или a,b.
Давай посмотрим на длину
добавление а и х в пустую строку
- State1 - 0 + 1 (x)
- State2 - 0
- Состояние 3 - 0 + 1 (а)
- State4 - 0
- State5 - 0
Всего 2
добавление б и х
- State1 - 1
- Состояние 2 - 0 + 1 (из состояния 1, добавив b)
- State3 - 1
- State4 - 0 + 1 (из state3 путем добавления b)
- State5 - 0
Всего 4
добавив а и х
- State1 - 1
- State2 - 1
- State3 - 1 + 1 (из состояния1 путем добавления к нему) + 1 (из состояния3 самого axa..)
- State4 - 1
- State5 - 0 + 1 (из stat2, добавив к нему)
Всего 7
Добавление б и х
- State1 - 1
- Состояние 2 - 1 + 1 (из состояния 1) + 1 (из самого состояния 2) + 1 (из состояния 4)
- State3 - 3
- Состояние 4 - 1 + 3 (из состояния 3)
- State5 - 1
Total 13Добавление а и х
- State1 - 1
- State2 - 4
- Состояние 3 - 3 + 1 (из состояния 1) + 3 (из самого состояния 3) + 1 (из состояния 5)
- State4 - 4
- Состояние 5 - 1 + 4(из состояния 2)
Total 22
Сложность будет O (n)
код будет добавлен в ближайшее время