洛谷题单指南-动态规划2-P4933 大师

原题链接：https://www.luogu.com.cn/problem/P4933

题意解读：求有多少个子序列可以组成等差序列

解题思路：

1、暴力DFS

如果实在想不出动规的方法，对于n<=20的数据，可以DFS枚举所有子序列的子集，再判断是否是等差数列。

30分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1000, MOD = 998244353;
int h[N], n, ans;
int a[N], b[N]; //a对应的h选则填1，不选则填0;b存选中的数

void dfs(int k)
{
    if(k > n)
    {
        //判断是否是等差数列
        int cnt = 0;
        for(int i = 1; i <= n; i++)
        {
            if(a[i]) b[++cnt] = h[i];
        }
        if(cnt == 0) return;
        if(cnt == 1 || cnt == 2) ans = (ans + 1) % MOD;
        else
        {
            for(int i = 3; i <= cnt; i++)
            {
                if(b[i] - b[i-1] != b[i-1] - b[i-2]) return;
            }
            ans = (ans + 1) % MOD;
        }
        
        return;
    }
    
    for(int i = 0; i <= 1; i++) //第k个可以选或者不选
    {
        a[k] = i;
        dfs(k + 1);
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    dfs(1);
    cout << ans;

    return 0;
}

2、动态规划1

设dp[i][j]表示以i，j为最后两位的等差数列个数，状态如何转移？

枚举i前面的所有k，只要h[i]-h[k] == h[j]-h[i]，则可以从dp[k][i]转移到dp[i][j]，dp[i][j] += dp[k][i]即可，注意取模

对于dp[][]的初始化，对于每一对dp[i][j]，初始值都dp[i][j]=1，也就是两个数也是一组等差数列

把所有dp[i][j]加起来即可，另外因为一个数也是等差数列，答案再加上n

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1000, MOD = 998244353;
int h[N], n, ans;
int dp[N][N]; //dp[i][j]表示以i，j为最后两位的等差数列个数

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];

    for(int j = 2; j <= n; j++)
    {
        for(int i = 1; i < j; i++)
        {
            dp[i][j] = 1;  //i，j组成的两位序列也是一个等差序列
            for(int k = 1; k < i; k++)
            {
                if(h[i] - h[k] == h[j] - h[i]) 
                    dp[i][j] = (dp[i][j] + dp[k][i]) % MOD;
            }
            ans = (ans + dp[i][j]) % MOD;
        }
    }
    ans = (ans + n) % MOD; //加上长度为1的序列个数
    cout << ans;

    return 0;
}

3、动态规划2

设dp[i][j]表示以i结尾，公差为j的等差数列个数，状态如何转移？

枚举i前面的所有k，计算公差h[i]-h[k]，直接基于公差h[i]-h[k]进行转移dp[i][h[i]-h[k]] += dp[k][h[i]-h[k]]

由于公差可能为负数，塔高1~20000，h[i]-h[k]要加上20000可以确保正数：dp[i][h[i]-h[k]+20000] += dp[k][h[i]-h[k]+20000]

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005, V = 20000, M = 40005, MOD = 998244353;
int h[N], n, ans;
int dp[N][M]; //dp[i][j]表示以i结尾，公差为j的等差数列个数，状态如何转移？

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];

    for(int i = 2; i <= n; i++)
    {
        for(int k = 1; k < i; k++)
        {
            dp[i][h[i] - h[k] + V] += dp[k][h[i] - h[k] + V] + 1; //k，i两个数也可以组成一个等差数列,所以要加上1
            dp[i][h[i] - h[k] + V] %= MOD;
        }
    }
    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            ans = (ans + dp[i][j]) % MOD;
        }
    }
    ans = (ans + n) % MOD;
    cout << ans;

    return 0;
}