线性 dp 学习

skyx · 2025-11-23 21:07:52 · 个人记录

P2362 围栏木桩

求每组数据的最长非递减子序列长度 t 及其方案数 c。

长度是容易的，考虑方案求法。

定义 c[i]：以第 i 个木桩结尾的、长度为 f[i] 的非递减子序列的方案总数。

初始化：最开始只有一个木桩时，c[1] = 1

转移方程：若 a[j] ≤ a[i] 且 f[j] + 1 = f[i]，则 c[i] += c[j]

边界处理：后面如果一个位置 i 没有任何前驱能转移来，即第 i 个木桩前面没有比它低的木桩可以接上，c[1] = 1

这样实现：

for(int i=2;i<=n;i++)
{
    for(int j=1;j<i;j++)
    {
        if(f[j]+1==f[i] && a[j]<=a[i]) c[i]+=c[j];
    }
    if(c[i]==0) c[i]=1;
}

结果求法：所有 f[i] == ans 的 c[i] 累加得到总方案数 cnt

P2008 大朋友的数字

和的处理？和转移一起 dp。

int a[N];
int dp[N];      // 以 i 结尾的 LNDS 长度
int sumv[N];   // 以 i 结尾的 LNDS 的最小和（字典序最小）

int main()
{
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for(int i=1; i<=n; i++)
    {
        // 初始化：每个节点自身可以作为长度为 1 的不下降序列
        dp[i] = 1;
        sumv[i] = a[i];

        // 尝试接前面的 j
        for(int j = 1; j < i; j++)
        {
            if(a[i] >= a[j])   // 能接上
            {
                // 情况 1：发现更长的 LNDS
                if(dp[j] + 1 > dp[i])
                {
                    dp[i] = dp[j] + 1;
                    sumv[i] = sumv[j] + a[i];
                }
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        cout << sumv[i] << " ";
    }
    cout<<endl;
    return 0;
}

[USACO ?] Generic Cow Protests

隔离成若干个小组，每个小组内的奶牛的理智度总和都要不小于零。

类似于各种子序列的状态定义。

dp[i]：到第 i 头牛为止，最多分成的组。

尝试把 i-j 分到一段，实际上是从 j-1 转移过来。

条件？和非负啊。进一步的，前缀和维护。还有在欲想使用 dp[j-1] 前，要保证它前面是一个合法方案。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e4+10;
int a[N];
int pre[N];
int dp[N];//到第 i 头牛为止，最多分成的组。

int main()
{
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pre[i]=pre[i-1]+a[i];
        dp[i] = -1;
    }
    if(pre[n]<0) 
    {
        cout<<"Impossible"<<endl;
        return 0;
    }
    dp[0]=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            if( pre[i]-pre[j-1]>=0 && dp[j-1]!=-1 ) dp[i]=max(dp[i],dp[j-1]+1);
            // 把 i-j 分到一段 实际上 从 j-1 转移过来。
            // 尝试的是 1 to i-1 注意实现。
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}