CF1811G2 题解

· · 题解

纪念一下第一次不看题解，不看算法标签做出 CF 评分 2200。
虽然实际上最多提高组 T1。

G1 做法

G2 做法只需要在 G1 基础上稍微修改。

很自然想到设 dp_{i,j} 表示第 i 位是路径的第 j 个点的方案数。

想一下如何转移，对于 i = 1，显然方案数是 1。
对于 i \ge 2，分一下类：

  1. 若 i \equiv 1 \pmod k，那么对于所有 j \le i-1，从 dp_{j,i-1} 转移，颜色不用管。
  2. 否则，还要在情况 1 的基础上加上一条限制：第 i 个点与 j 点颜色相同。

主要思想就是这个。

关于怎么统计之前符合某些条件的状态答案综合，这个开个数组记一下就行了，都把 dp 设计出来了，这么简单的想必都会。

剩下的就是从大到小枚举 m，每次跑一遍 dp，找到答案就终止。

dp 复杂度 O(n^2)。

枚举最劣复杂度 O(n)。

总复杂度 O(n^3)。

G2 做法

dp 不大可能优化了，看枚举过程很方便优化。

主要就是优化寻找最长路径长度的过程。

我们可以先做一遍 dp，看路径长度最高到多少，使得答案不为 0。

然后对这个路径长度 dp 一下就行了。

UPD：做法麻烦了，实际上直接 dp 一遍就行了。

Code

// LUOGU_RID: 107120197
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back()
#define mkpr make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 5005;
typedef long long ll;
const ll mod = 1e9 + 7;
int t;
int n, k;
int c[maxn];
ll dp[maxn][maxn];  // 第 i 位状态为 j
ll sum[maxn][maxn]; // 颜色为 i，状态为 j，dp 值和
ll sum2[maxn];      // 状态为 i dp 总和
bool dp2[maxn][maxn],sum21[maxn][maxn],sum22[maxn];
inline int turn(int status)
{
    if (status % k == 0)
        return k;
    return status % k;
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &k);
        FOR(i, 1, n)
        {
            scanf("%d", &c[i]);
        }
        ll ans = 0;
        FOR(i, 1, n)
        {
            dp2[i][1]=1;
            FOR(j, 2, n)
            {
                if (turn(j) == 1)
                {
                    dp2[i][j]|=sum22[j-1];
                }
                else
                {
                    dp2[i][j]|=sum21[c[i]][j-1];
                }
            }
            FOR(j, 1, n)
            {
                sum22[j] |= dp2[i][j];
                sum21[c[i]][j] |= dp2[i][j];
            }
        }
        int blocks = n / k;
        bool isansoutputed=0;
        for (int m = blocks * k; m > 0; m -= k)
        {
            bool flag = 0;
            FOR(i, 1, n)
            {
                if (dp2[i][m])
                {
                    flag = 1;
                    break;
                }
            }
            if (flag)
            {
             //   printf("m = %d\n", m);
                FOR(i, 1, n)
                {
                    dp[i][1] = 1;
                    FOR(j, 2, m)
                    {
                        if (turn(j) == 1)
                        {
                            dp[i][j] += sum2[j - 1];
                        }
                        else
                        {
                            dp[i][j] += sum[c[i]][j - 1];
                        }
                        dp[i][j] %= mod;
                    }
                    FOR(j, 1, m)
                    {
                        sum2[j] += dp[i][j];
                        sum2[j]%=mod;
                        sum[c[i]][j] += dp[i][j];
                        sum[c[i]][j] %= mod;
                    }
                }
                FOR(i, 1, n)
                {
                    ans += dp[i][m];
                    ans%=mod;
                    FOR(j, 1, n)
                    {
                        //    printf("dp[%d][%d] = %d\n",i,j,dp[i][j]);
                        dp[i][j] = 0;
                        sum[i][j] = 0;
                    }
                    sum2[i] = 0;
                }
                isansoutputed=1;
                break;
            }
        }
        if (!isansoutputed)
            ans++;
        printf("%lld\n", ans % mod);
        FOR(i, 1, n)
        {
            sum2[i] = sum22[i]=0;
            FOR(j, 1, n)
            {
                dp[i][j] = dp2[i][j]=0;
                sum[i][j] = sum21[i][j]=0;
            }
        }
    }
    return 0;
}