线性DP

Posted by

codeforce 1389 B. Array Walk

题解

dp[i][j] 为在i的位置,已经向左移动了j次的最大和

对于直接向右行走有:
dp[i][j]=dp[i-1][j]+a[i]
并且在i-1+j*2==k时需要取ans的最大值,因为此时是刚好步数达到要求时的状态,其中2*j是因为要在ii-1之间反复行走,所以前面的项是i-1.

对于向左移动的行走有:
dp[i-1][j+1]=max(dp[i-1][j+1],dp[i][j]+a[i-1])
这个转移是显然的,即在i处向左走到i-1的位置,并且向左操作数加了一.注意这个转移是只能在j+1<=z时才能发生的.
当这种转移结束后,应当再比较一次最大值的变化.即(i-1)-1+(j+1)*2==k,因为又向左了一步,那么就是在i-1-1i-1之间反复行走了.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t, n, a[100010], k, z, sum[100010];
int dp[100010][6];

int main()
{
    scanf("%d", &t);
    while (t --)
    {
        memset(dp, 0, sizeof(dp));
        scanf("%d %d %d", &n, &k, &z);
        for (int i = 1; i <= n; i ++) 
            scanf("%d", &a[i]);
        z = min(z, 5);
        int ans = -1;
        for (int i = 1; i <= n; i ++)
        {
            for (int j = 0; j <= z; j ++)
            {
                dp[i][j] = dp[i-1][j] + a[i];
                if (i - 1 + 2 * j == k) ans = max(ans, dp[i][j]);
                if (j + 1 <= z) dp[i-1][j+1] = max(dp[i-1][j+1], dp[i][j] + a[i-1]);
                if ((i - 1) - 1 + 2 * (j+1) == k) ans = max(ans, dp[i-1][j+1]);
            }
        }
        printf("%dn", ans);
    }
    return 0;
}

codeforce 1272 D. Remove One Element

题解

两次LIS,f(i)为以i结尾的最长上升子序列大小,g(i)为以i开头的最长上升子序列大小.
使用经典的LIS做法进行两种状态转移.枚举每一个i,i为被删除的数据,并且有i in [2,n-1].

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
ll a[200010], f[200010], g[200010];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        scanf("%lld", &a[i]);
    f[1] = 1;
    g[n] = 1;
    for (int i = 2; i <= n; i ++)
    {
        if (a[i-1] < a[i]) f[i] = f[i-1] + 1;
        else f[i] = 1;
    }
    for (int i = n - 1; i >= 1; i --)
    {
        if (a[i] < a[i+1]) g[i] = g[i+1] + 1;
        else g[i] = 1;
    }
    ll ans = -1;
    for (int i = 1; i <= n; i ++) ans = max(ans, f[i]);
    for (int i = 2; i <= n - 1; i ++ ) 
        if (a[i-1] < a[i+1]) ans = max(ans, f[i-1] + g[i+1]);
    printf("%lldn", ans);
    return 0;
}

codeforces 1307

题解

只考虑一位和两位的情况,记f(i,j)为以i为第二位,j为第一位的当前长度为2的子串数量.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

string ss;
ll dp[100010][30], cnt[100010];


int main()
{
    cin >> ss;
    ll ans = -1;
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < ss.size(); i ++)
    {
        int t = ss[i] - 'a';
        for (int j = 0; j < 27; j ++)
        {
            dp[t][j] = dp[t][j] + cnt[j];
            ans = max(ans, dp[t][j]);
        }
        cnt[t] ++;
        ans = max(cnt[t], ans);
    }
    printf("%lld\n", ans);

    return 0;
}

浙江省省赛G题 G. Gliding

题解

题解

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注