题解 - Vijos

2

zyc2000 LV 9 @ 2018-02-13 21:20:08

题目难点在于边界： 这道题目虽然也是从区间长度小往区间长度大推，但是不同于普通的区间dp，这道题因为指针的存在 不能从头扫到尾 ，而是要 从上一次指针边界往左往右各加一格，长度加1 的方式递推。

递推方程

dp[l][r]表示区间，[0][1]表示指针位于左边/右边，pmaxp表示区间l-r外最大数字
dp[l][r][0] = min(dp[l+1][r][0]+pmaxp[l+1][r], dp[l+1][r][1]+pmaxp[l+1][r]*(r-l-2*k));
      dp[l][r][1] = min(dp[l][r-1][1]+pmaxp[l][r-1], dp[l][r-1][0]+pmaxp[l][r-1]*(r-l-2*k));

虽然AC了，但是内存使用有点大，不知道怎么优化。推最大值的算法pmax和pmaxp可能有点朴素，都是O(n^2)的复杂度，不知道有没有办法优化到O(nlogn)或O(n)，（线段树/单调栈？）求指教。
这段代码是卡着时限/空间限制AC的，卡一下常数就挂了，还需优化。

#include<cstdio>
#include<iostream>
#define MAXN 4005
#define INF 2100000000
using namespace std;

int n, k, a[MAXN];
int p[MAXN], plen, pcenter;
int pmax[MAXN][MAXN] = {0}, pmaxp[MAXN][MAXN] = {0};
int dp[MAXN][MAXN][2];

int main(){
  int nsum = 0;
  cin >> n >> k;
  for(int i=0; i<n; i++){
    cin >> a[i];
    nsum += a[i];
    a[i+n] = a[i];
  }
  plen = 2*n-2*k-1;
  pcenter = n-k;
  for(int i=1; i<=plen; i++){
    p[i] = a[i+k];
    pmax[i][i] = p[i];
    // cout << p[i] << " ";
  }
  // cout << endl;
  // cout << endl << pcenter << endl;
  for(int len=1; len<n; len++){
    for(int l=1, r; (r=l+len)<=plen; l++){
      pmax[l][r] = max(pmax[l][r-1], pmax[r][r]);
      // cout << pmax[l][r] << " ";
    }
    // cout << endl;
  }
  for(int len=1; len<n; len++){
    for(int l=1, r; (r=l+len)<=plen; l++){
      int lpos = max(0, r-n);
      pmaxp[l][r] = max(pmax[lpos+1][l-1], pmax[r+1][lpos+n]);
      // cout << l << " " << r << " : " << lpos+1 << " " << l-1 << " | " << r+1 << " " << lpos+n << " " << pmaxp[l][r] << endl;
      // cout << pmaxp[l][r] << " ";
    }
    // cout << endl;
  }
  for(int i=1; i<=plen; i++){
    for(int j=1; j<=plen; j++){
      dp[i][j][0] = dp[i][j][1] = INF;
    }
  }
  int minans = INF;
  dp[pcenter-k][pcenter+k][0] = dp[pcenter-k][pcenter+k][1] = 0;
  for(int pl=1; pl<pcenter-k; pl++){
    for(int l=pcenter-pl-k, r; (r=l+pl+k*2)<=pcenter+pl+k; l++){
      dp[l][r][0] = min(dp[l+1][r][0]+pmaxp[l+1][r], dp[l+1][r][1]+pmaxp[l+1][r]*(r-l-2*k));
      dp[l][r][1] = min(dp[l][r-1][1]+pmaxp[l][r-1], dp[l][r-1][0]+pmaxp[l][r-1]*(r-l-2*k));
      // cout << l << " " << r << " : ";
      // cout << dp[l][r][0] << " " << dp[l][r][1] << endl;
      if(pl == pcenter-k-1){
        minans = min(minans, dp[l][r][0]);
        minans = min(minans, dp[l][r][1]);
      }
    }
    // cout << endl;
  }
  cout << minans + nsum << endl;

  return 0;
}

评测情况

Accepted
#   状态  耗时  内存占用
#1  Accepted    2ms     4.5 MiB
#2  Accepted    3ms     6.34 MiB
#3  Accepted    8ms     14.625 MiB
#4  Accepted    8ms     16.375 MiB
#5  Accepted    28ms    48.625 MiB
#6  Accepted    36ms    62.75 MiB
#7  Accepted    185ms   118.375 MiB
#8  Accepted    446ms   189.125 MiB
#9  Accepted    577ms   236.617 MiB
#10     Accepted    575ms   240.875 MiB

1

shisuan LV 8 @ 2018-07-25 12:05:49

dp[i][j][k]为第i个到第j个还没取走，k=0时在左边，k=1时在右边。
就有状态转移方程
dp[i][j][1]=min(dp[i][j][1],dp[i][j+1][1]+check[i][j+1]);
dp[i][j][1]=min(dp[i][j][1],dp[i][j+1][0]+check[i][j+1]*(n-2+i-j-2*k));
dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]+check[i-1][j]);
dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][1]+check[i-1][j]*(n-2+i-j-2*k));

#include<stdio.h>
#include<algorithm>
#include<string.h>
#define inf 0x3f3f3f3f
using namespace std;
int a[4005];
int dp[2005][2005][2];
int check[2005][2005];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    memset(dp,inf,sizeof(dp));
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        a[i+n]=a[i];
    }
    int sum=0;
    for(int i=0;i<n;i++)
    {
        sum+=a[i];
        int ans=0;
        for(int j=i;j<n;j++)
        {
            if(a[j]>ans)
            {
                check[i][j]=a[j];
                ans=a[j];
            }
            else
            check[i][j]=ans;
            //printf("%d ",ans);
        }
        //printf("\n");
    }
    for(int i=k+1;i<=(n-k-1)%n;i++)
    {
        for(int j=(n-k-1)%n;j>=i;j--)
        {
                if(i==k+1||j==(n-k-1)%n)
                {
                    if(i==k+1&&j==(n-k-1)%n)
                    {
                    dp[i][j][1]=0;
                    dp[i][j][0]=0;  
                    }
                    else if(i==k+1)
                    {
                        dp[i][j][1]=min(dp[i][j+1][1]+check[i][j+1],dp[i][j+1][0]+check[i][j+1]*(n-2+i-j-2*k));
                    }
                    else
                    {
                    dp[i][j][0]=min(dp[i-1][j][0]+check[i-1][j],
                    dp[i-1][j][1]+check[i-1][j]*(n-2+i-j-2*k));
                    }
                    
                }
                else
                {
                dp[i][j][1]=min(dp[i][j][1],dp[i][j+1][1]+check[i][j+1]);
                dp[i][j][1]=min(dp[i][j][1],dp[i][j+1][0]+check[i][j+1]*(n-2+i-j-2*k));
                
                
                dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]+check[i-1][j]);
                dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][1]+check[i-1][j]*(n-2+i-j-2*k));
                }
            }
            //printf("%d %d %d\n",i,j,dp[i][j]);
        }
    int ans=inf;
    for(int i=k+1;i<=(n-k-1)%n;i++)
    {
    ans=min(ans, dp[i][i][0]+check[i][i] );
    ans=min(ans,dp[i][i][1]+check[i][i] );
    }
    
    printf("%d\n",ans+sum);
    return 0;
}

Goodhao @ 2020-07-20 18:14:31

6 1
1 10 2 1 7 6
你的答案是37但是这个应该是38？

1

ipip2005 LV 10 @ 2008-09-22 13:30:02

首先把可以取的那一块取完，以后每个数只要掉进范围里就取，问题就转换成头尾取数型的DP了，代价也可以求

1

fjxmlhx LV 10 @ 2008-09-21 19:23:11

容易知道ans=sum+移动代价。

显然在移动的时候不取白不取（不取难道你要再回来取？），现在剩下多少数没有取可以用一个二维状态表示

0

王栋栋 LV 8 @ 2014-07-17 14:25:51

ORZ

0

Jungle LV 10 @ 2009-11-02 09:00:29

orz楼下wlf神牛和jacky神牛

0

秋疯扫弱叶 LV 10 @ 2009-10-30 12:08:59

orz LX jacky神牛- -

我能AC是踩在jacky的肩膀上~严重澳淄

0

db_db_Jacky LV 10 @ 2009-10-30 09:01:44

这题实在太猥琐了。。受不了。。

提几个注意事项吧

首先状态转移注意边界。

f

k=0表示指针在i右边取到j

k=1表示指针在j左边取到i

f与f和f有关

f与f和f有关

还有过程量 f数组longint足够。。不过在状态转移时可能生成比longint大的数

为了防止216我们设定最大值。如果过程量>最大值就赋值成最大值。。

。。。0 0 0 0 70 0 0 0 0。。。。 70 70 100AC。。非常之邪恶

膜拜此题~~~

0

lc_jack LV 9 @ 2009-10-23 18:15:28

转移方程：左边取i个，右边取j个。

t :=Maxnum(1+k+i,n+1-k-j-1);

if i >0 then f[i][j][0] :=min(f[j][0]+t ,f[j][1]+t * (i+j) )

else f[i][j][0] :=Inf;

t :=Maxnum(1+k+i+1,n+1-k-j);

if j >0 then f[i][j][1] :=min(f[i][j-1][1]+t ,f[i][j-1][0]+t * (i+j) )

else f[i][j][1] :=Inf;

边界：

f[0][0][0] = 0

f[0][0][1] = 0

0

lianggj2 LV 8 @ 2009-09-24 12:06:28

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：50ms

第一步: 要想到贪心,把附近的先取了.

第二步: 变成了一行数,从两头取的dp.

第三步: 其实可以不记当前指针在那里,只需要记当前指针是距离左边k+1处,或者是在距离右边k+1处. 状态是f[n][n][2]即可.

0

zhanghanyuan LV 10 @ 2009-09-14 20:59:39

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 306ms

├ 测试数据 09：答案正确... 274ms

├ 测试数据 10：答案正确... 259ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：848ms

悲剧

0

xjcjason123 LV 10 @ 2009-08-19 08:58:29

额。。指针可以随便乱转吗？

0

king13 LV 8 @ 2008-09-24 19:09:30

问下大牛:这题能用贪心做吗?指点一下,有的发给我一下king13hu@sina.com谢拉不过用DP也能过哈哈我只是想知道贪心是否可以大牛们一定要发给我拉不胜感激编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 56ms├ 测试数据 10：答案正确... 9ms-------------------------Accepted 有效得分：100 有效耗时：65ms

0

kjijkbo LV 8 @ 2008-09-24 13:42:15

此题!建立在画图人工测试数据的基础上,..终于理解了

0

Fengyunfly LV 8 @ 2008-09-23 22:54:21

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 103ms

├ 测试数据 10：答案正确... 119ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：278ms

0

tracy-henry LV 10 @ 2008-09-23 21:00:25

这个贪心让人费解。难道没有严格的证明？

0

imhy12 LV 3 @ 2008-09-23 20:25:52

哪位可以讲解一下吗？

-1

一方T行 LV 10 @ 2014-08-20 22:30:20

orz教主

-1

xujiahe LV 10 @ 2014-08-06 19:51:01

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
int save[4100];
int n,m,dp[2100][2100][2];
int d2[200005][100],a[200005];
int Min(int a,int b)
{
return a>b?b:a;
}
int Max(int a,int b)
{
return a>b?a:b;
}
void init()
{
int k=(int)log2(n);
for(int i=1;i<=n;i++)
d2[i][0]=save[i];
for(int j=1;j<=k;j++)
{
for(int i=1;i+(1<<(j-1))<=n;i++)
d2[i][j]=Max(d2[i][j-1],d2[i+(1<<(j-1))][j-1]);
}
}
int RMQ(int l,int r)
{
if(r<l) return 0;
int k=(int)log2(r-l+1);
int MAX = Max(d2[l][k],d2[r-(1<<k)+1][k]);
return MAX;
}
inline int ReadInt()
{
int flag=0;
char ch = getchar();
int data = 0;
while (ch < '0' || ch > '9')
{
if(ch=='-') flag=1;
ch = getchar();
}
do
{
data = data*10 + ch-'0';
ch = getchar();
}while (ch >= '0' && ch <= '9');
if(flag) data=-data;
return data;
}
int main()
{
n=ReadInt();
m=ReadInt();
int ans=0;
for(int i=1;i<=n;i++)
{
save[i]=ReadInt();
ans+=save[i];
}
init();
dp[0][0][1]=0;
dp[0][0][0]=0;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=(n-i);j++)
{
if(i==0&&j==0) continue;
int maxn = 0;
maxn=RMQ(1+m+i,n-m-j);
if (i >0)
dp[i][j][0]=Min(dp[i-1][j][0]+maxn,dp[i-1][j][1]+maxn*(i+j) );
else
dp[i][j][0]=0x3f3f3f3f;
maxn=RMQ(1+m+i+1,n-m-j+1);
if (j >0 )
dp[i][j][1]=Min(dp[i][j-1][1]+maxn ,dp[i][j-1][0]+maxn*(i+j) );
else
dp[i][j][1]=0x3f3f3f3f;
}
}
int tmp=0x3f3f3f3f;
for(int i=0;i<=n;i++)
{
tmp=Min(tmp,Min(dp[i][n-i][0],dp[i][n-i][1]));
}
printf("%d\n",tmp+ans);
return 0;
}

-1

sad12315 LV 6 @ 2012-10-20 16:13:02

├ 测试数据 01：答案正确... (0ms, 48116KB) ├ 测试数据 02：答案正确... (0ms, 48116KB) ├ 测试数据 03：答案正确... (0ms, 48116KB) ├ 测试数据 04：答案正确... (0ms, 48116KB) ├ 测试数据 05：答案正确... (0ms, 48116KB) ├ 测试数据 06：答案正确... (0ms, 48116KB) ├ 测试数据 07：答案正确... (0ms, 48116KB) ├ 测试数据 08：答案正确... (0ms, 48116KB) ├ 测试数据 09：答案正确... (0ms, 48116KB) ├ 测试数据 10：答案正确... (0ms, 48116KB)

---|---|---|---|---|---|---|---|-Accepted / 100 / 0ms / 48116KB

题解

35 条题解

圆环取数

信息

状态

开发

支持

题解

35 条题解

圆环取数

信息

状态

开发

支持

还没有账户？

登录