题解 P3860 【[TJOI2009]火星人的手机】

GNAQ · 2019-01-22 20:41:18 · 题解

一血补题解

DP with 记录前驱

当时的省选前几题好简单……

发现题意模糊不清，结合样例认真理解一下发现是区间划分 DP 。

观察数据范围 易得复杂度是 O(n^2m) 级别的。 （不过好像可以上斜率 DP 或者之类的东西优化？

先预处理 val[i][j] 表示从 i 到 j 划出一个键总共要按多少次。

这是 O(n^2) 的。

for (int i=1;i<=n;i++)
     for (int j=i;j<=n;j++)
         vals[i][j]=vals[i][j-1]+seq[j]*(j-i+1);

然后直接 DP 。简单区间 DP 常见套路：设 dp[i][j] 表示到了字母 i ，划出了 j 个键，然后转移就枚举当前字母所在的键是多大。

dp[i][j]=min(dp[i][j],dp[pre_pos][j-1]+vals[pre_pos+1][i]);

然后输出方案的话要记录一下前驱。

细节：可能有 m>n ，根据题意，前面要划出 m-n 个 0 字母键。

#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;

int n,m,seq[5010],pre[510][110],mm;
ll vals[510][510],dp[510][110];

template<typename int_t>
void readx(int_t& x)
{
    x=0; int_t k=1; char ch=0;
    while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}

void Output(int now,int grp)
{
    if (grp)
    {
        Output(pre[now][grp],grp-1);
        printf("%d\n",now-pre[now][grp]);
    }
}

int main()
{
    readx(n); readx(m); mm=m; m=min(m,n);
    for (int i=1;i<=n;i++) readx(seq[i]);

    // init vals
    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j++)
            vals[i][j]=vals[i][j-1]+seq[j]*(j-i+1);

    for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) dp[i][j]=1e16;
    dp[0][0]=0; 
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=min(i,m);j++)
        {
            for (int k=0;k<=i-1;k++) // the last group
            {
                if (dp[k][j-1]+vals[k+1][i]<dp[i][j])
                {
                    dp[i][j]=dp[k][j-1]+vals[k+1][i];
                    pre[i][j]=k;
                }
            }
        }
    }

    printf("%lld\n",dp[n][m]);
    if (mm) for (int i=n+1;i<=mm;i++) printf("0\n");
    Output(n,m);
}