codeforces 474D.Flowers 解题报告

题目链接：http://codeforces.com/problemset/problem/474/D

题目意思：Marmot 吃两种类型的花（实在难以置信呀～～）：red 或者 white，如果要吃到white这种花，就需要吃连续 k 朵 white；而如果吃 red，就没有这种限制。给定区间[a, b]，问总共的吃法有多少种。

dp 题！状态转移方程不难得到。设 dp[i] 表示长度为 i 时的吃法种数。

dp[i] = dp[i-1] + dp[i-k]

对于当前 i，或者是从第 i-1 条长度后直接添加 red，又或者在 i-k 的长度后添加 white。这两种情况都添加完之后长度都变为 i 了。

不过有个数学问题错了 n 次。当大于 1e9+7时，需要减去 1e9 + 7。还有，处理dp的值时要离线处理，否则TLE。这意味着要用多一个数组sum。

sum[i]表示长度为到达长度为 i 时一共的吃法种数（有点拗口），与dp[i]是不同的，是累加呀～～～

话说我是看了tourist 对这个 1e9+7 的处理才改对的。他代码非常精简：

　　http://codeforces.com/submissions/tourist

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 const int MOD = 1e9+;

 const int maxn = 1e5 + ;

 int dp[maxn], sum[maxn];

 int main()

 {

     int t, k, a, b;

     #ifndef ONLINE_JUDGE

         freopen("in.txt", "r", stdin);

     #endif

     while (scanf("%d%d", &t, &k) != EOF)

     {

         memset(dp, , sizeof(dp));

         memset(sum, , sizeof(sum));

         for (int i = ; i <= k; i++)   // 前 k 个长度只能不断添加R这种花

         {

             dp[i]++;

             sum[i] = sum[i-] + dp[i];

         }

         dp[k]++;      // 到达 k 这个长度表示可以添加第一个W这种花了

         sum[k]++;     // 加多一种只吃 W 的情况

         for (int i = k+; i <= maxn; i++)

         {

             dp[i] = (dp[i-k] + dp[i-]);

             dp[i] = (dp[i] >= MOD ? dp[i]-MOD : dp[i]);

             sum[i] = (sum[i-] + dp[i]);

             sum[i] = (sum[i] >= MOD ?  sum[i]-MOD : sum[i]);

         }

         while (t--)

         {

             scanf("%d%d", &a, &b);

             printf("%d\n", (sum[b]-sum[a-]+MOD) % MOD);  // 这个很关键

         }

     }

     return ;

 }

巴特西

codeforces 474D.Flowers 解题报告

最新文章

热门文章