网站搜索框用ps怎么做/汕头网站建设

传送门

题意：说了给出n个位置，至少要填m个G，至多要填k个R，P无所谓

题解：首先至少至多需要统一，都统一成至多，那么至少要填m个G怎么转化，转化成至多填n个G，至多填k个R的方案个数减去至多填m-1个G，至多填k个R的方案个数就是至少要填m个G，至多要填k个R的方案个数，然后考虑这个位置是填G,R,P这三种的哪一种？

设dp[i][0]为这一位填G，且符合大条件下的方案个数，设dp[i][1]为这一位填R，且符合大条件下的方案个数，设dp[i][2]为这一位填P，且符合大条件下的方案个数，此处的大条件为传进去的条件，比如至多填n个G，至多填k个R。

然后对于这一位填P，直接递推位dp[i][2]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]

其他两种需要仔细讨论一番，如果i<=u，那么证明G还没有填满，直接递推为dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]

如果i==u+1，那么此处的递推就需要减去前面有一种前u位都是G的情况，递推方程为dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-1

如果i>u+1，那么就需要另外考虑了，需要减去的是从第i-1位到第i-u-1都是G的情况了，那么此处应该怎么减呢？是不是应该减去第i-u-1位为R和P的方案个数之和，并且不用减去第i-u-1位为G的方案个数，那么就可以递推了，dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-dp[i-u-1][1]-dp[i-u-1][2]

同样对于R的情况也是这样的

巨坑：这个题不仅仅这样，我还是不够老道，对于减的取余问题，我这个点WA了好几发，减的取余问题一定要写成((a1-a2)%mod)+mod)%mod的形式，一定不能写成(a1-a2+mod)%mod，突然感觉自己好傻。

附上代码：

#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=1000000007;
const ll maxn=1e6+5;ll n,m,k;
ll dp[maxn][3];ll cal(ll u,ll v)
{dp[0][0]=1;dp[0][1]=dp[0][2]=0;for(ll i=1;i<=n;i++){ll sum=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%mod;dp[i][2]=sum;if(i<=u){dp[i][0]=sum;}else if(i==u+1){dp[i][0]=(sum-1)%mod;}else{dp[i][0]=(sum-dp[i-u-1][1]-dp[i-u-1][2])%mod;}if(i<=v){dp[i][1]=sum;}else if(i==v+1){dp[i][1]=(sum-1)%mod;}else{dp[i][1]=(sum-dp[i-v-1][0]-dp[i-v-1][2])%mod;}}return (dp[n][0]+dp[n][1]+dp[n][2])%mod;
}int main()
{while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF){printf("%lld\n",((cal(n,k)-cal(m-1,k))%mod+mod)%mod);}return 0;
}