Я столкнулся с этой проблемой dp. Это выглядит следующим образом: -
Арья Старк и Санса Старк - сестры, но часто сражаются друг с другом по той или иной причине. Недавно Санса избила Арью, обманув в охоте, и высмеяла ее. Арья полна гнева и хочет отомстить. Арья позвала свою старшую сестру Сансу для битвы, и Санса приняла ее.
Битва состоит из R раундов, где в каждом раунде будет проверяться отдельный навык. Навык может быть стрельба из лука, борьба с мечом или что-то еще. После каждого раунда победителю раунда присуждается очко. После того, как все R раунды проведены, тот, кто набрал максимальное количество очков, считается победителем.
Арья злится и хочет не просто выиграть битву, но победить Сансу таким образом, чтобы после каждого раунда ее очки были как минимум в P раз больше очков Сансы. Она занята подготовкой к битве и слышала о твоих навыках. Она хочет, чтобы вы нашли количество способов, которыми она может победить Сансу с предоставленным условием и отомстить.
Порядок выигрыша различает разные способы. Пример: давайте рассмотрим, есть 3 раунда.
Случай 1: Арья выиграла первый раунд, Санса - второй раунд, Арья - третий раунд
Порядок: - Арья, Санса, Арья
Случай 2: Арья выиграла первый раунд, Арья также выиграла второй раунд, а Санса выиграла третий раунд
Порядок: -Арья, Арья, Санса
Оба случая вышеотличаются друг от друга и считаются двумя разными способами.
Примечание. Поскольку ответ может быть большим, возьмите по модулю 10 ^ 9 + 7.
Формат ввода: первая строка ввода состоит из числа тестовых случаев, T единственная строкакаждый контрольный пример состоит из двух целых чисел R и P., разделенных пробелом.
Ограничения: 1 <= T <= 10 </p>
1 <= R <= 1000 </p>
1 <=P <= R </p>
Формат вывода: -
Для каждого теста выведите количество возможных путей в отдельной строке.
Образец TestCase 1
Вход
2 4 2 2 2
Выход
3
1
Объяснение Контрольный пример 1:
Есть три способа, которыми Арья может выиграть с данным условием
ПУТЬ 1: Первые три раунда выигрывает Арья, а Последний раунд выигрывает Санса
Арья, Арья, Арья, Санса
ПУТЬ 2: Первые два раунда выигрывает Арья. Третий раунд выигрывает Санса, а последний раунд выигрывает Арья.
Арья, Арья, Санса, Арья
ПУТЬ 3: Все четыре раунда выигрывает Арья.
Арья, Арья, Арья, Арья
Тестовый пример 2: В этом случае есть только один способ выиграть, т.е. если Арья выигрывает оба раунда.
Арья, Арья
Мой код проблемы: -
enter code gghere
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll e=1000000007;
ll a2[2000][2000];
int main()
{ll t;
cin>>t;
ll t1=t;
while(t--)
{
ll r,p;
cin>>r>>p;
//map<pair<ll,ll>,ll> a2;
//a2[{1,0}]=1;
a2[1][0]=1;
ll w[20000][9];
ll op=0;
w[op][0]=1;
w[op][1]=0;
w[op][2]=1;
op++;
ll i1=0;
ll i=2;
while(i<=r)
{
ll b[20000][7];
ll pass=0;
i1=0;
while(i1<op)
{
ll c1,c2;
ll c3;
c1=w[i1][0]%e;
c2=w[i1][1]%e;
c3=w[i1][2]%e;
if((c1+1)>=p*c2)
{
//....(c1+1,c2)+=c3
b[pass][0]=c1+1;
b[pass][1]=c2;
b[pass][2]=c3%e;
pass++;
}
if(c1>=p*(c2+1))
{
b[pass][0]=c1;
b[pass][1]=c2+1;
b[pass][2]=c3%e;
//.......(c1,c2+1)+=c3
pass++;
}
i1++;
}
i1=0;
while(i1<op)
{
ll x1=w[i1][0];
ll x2=w[i1][1];
a2[x1][x2]=0;
w[i1][0]=0;
w[i1][1]=0;
w[i1][2]=0%e;
i1++;
}
op=0;
ll j=0;
while(j<pass)
{
ll x1=b[j][0];
ll x2=b[j][1];
ll x3=b[j][2]%e;
if(a2[x1][x2]==0)
{
w[op][0]=x1;
w[op][1]=x2;
op++;
}
else
{
}
a2[x1][x2]=(a2[x1][x2]%e+x3%e)%e;
j++;
}
i1=0;
while(i1<op)
{
ll m1=w[i1][0];
ll m2=w[i1][1];
w[i1][2]=a2[m1][m2]%e;
i1++;
}
i++;
}
i1=0;
ll c4=0;
while(i1<op)
{
ll c1,c2;
ll c3;
c1=w[i1][0]%e;
c2=w[i1][1]%e;
//cout<<c1<<" "<<c2;
//cout<<"\n";
c3=w[i1][2]%e;
c4=(c4%e+c3%e)%e;
//cout<<c1<<" "<<c2<<" "<<c3<<"\n";
c4=c4%e;
i1++;
}
cout<<c4;
cout<<"\n";
ll o=0;
while(o<=1500)
{
ll p=0;
while(p<=1200)
{
a2[o][p]=0;
p++;
}
o++;
}
}
return 0;
}
Я хочу подтвердить правильность моего подхода, если так, то что мне нужно изменить? Могу ли я сделать это лучше?
Спасибо :-)