线性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

题解

题解

[ZJOI2004] 午餐

题解

考虑两种排序方式:
其中b_1>b_2

第一种:

  1. <a_1,b_1>
  2. <a_2,b_2>

排队加吃饭的总时间是t=a_1+a_2+b_2,因为第一个人排完队就直接去吃饭了,并且吃饭时间是被第二个人的排队和吃饭时间覆盖掉的。

第二种:

  1. <a_2,b_2>
  2. <a_1,b_1>

总时间t=a_1+a_2+b_1,原理同上。由于b_1>b_2,那么最优的排序方案应该是将吃饭时间大的人排在前面。

在排序完毕后做一个前缀和sum,表示前i个人排队用的时间sum[i] = sum[i-1] + s[i].a

f_{i,j}表示前i个人在1号打饭窗口,打饭总时间为j,最早吃完饭的时间。

对于第一个窗口的状态转移如下:

f_{i,j} = min(f_{i,j},max(f{i-1,j-s_{i,a}},j+s_{i,b}))

由于要新加入一个人,所以要比较当前加入的人和上一个人的吃完饭的时间,取最大。max中的状态转移可以类比背包动态规划的转移方式。

在第二个窗口的状态转移如下:

f{i,j} = min(f_{i,j}, max(f_{i-1,j}, sum_{i} – j + s_{i,b}))

sum_{i}-j为第二个窗口的总排队时间。

#include <bits/stdc++.h>

using namespace std;

int n;

struct stu
{
    int a, b;
} s[300];

int f[300][40010];
int sum[300];

bool cmp(stu x, stu y)
{
    return x.b > y.b;
}

int main()
{
    scanf("%d", &n);
    sum[0] = 0;
    for (int i = 1; i <= n; i ++)
    {
        scanf("%d %d", &s[i].a, &s[i].b);
    }
    sort(s + 1, s + 1 + n, cmp);
    for (int i = 1; i <= n; i ++)
        sum[i] = sum[i-1] + s[i].a;
    memset(f, 127, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= sum[i]; j ++)
        {
            if (s[i].a <= j)
            {
                f[i][j] = min(f[i][j], max(f[i-1][j-s[i].a], j + s[i].b));
            }
            f[i][j] = min(f[i][j], max(sum[i] - j + s[i].b, f[i-1][j]));
        }
    }
    int ans = 2147483647;
    for (int i = 1; i <= sum[n]; i ++) 
    {
        ans = min(ans, f[n][i]);
        // printf("%d\n", f[n][i]);
    }
    printf("%d\n", ans);
    return 0;
}

Leave a Reply

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