据说是CF div1的难度T^T 就只出了两个题,还是因为有一个是原题,昨天晚上做题居然又没想到dp滚动数组 dp啊 又爱又恨啊

第一次WA50%因为最大值取小了

https://www.nowcoder.com/acm/contest/56/B

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述 

codeJan 非常喜欢旅行。现在有 n 个城市排在一条线上,并且 codeJan 的位置不和任何一个城市的位置重叠。
codeJan 想要游览 m 个城市,同时因为时间是不断变化的,游览一个城市多次也是允许的,但是不能永远待在一个城市,否则那样太无聊了。给出这些城市的位置,codeJan 想要知道游览 m 个城市至少需要走多少米?

输入描述:

第一行是一个T≤20代表测试组数。
每组第一行是三个正整数n,m,p,分别代表城市数量、codeJan想要浏览的城市数量和codeJan当前的位置(单位为米)。
第二行包含n个正整数pos[i]表示第i个城市的位置,单位为米。
输入保证pos[i]<pos[i+1](i∈[1,n−1]),并且p ≠ pos[i](i∈[1,n])。

输出描述:

对于每组输入数据输出一个正整数表示 codeJan 至少需要走的距离。
示例1

输入

3 
2 2 2 
1 3 
2 2 1 
2 3 
4 3 4 
1 3 5 6

输出

3
2
3

说明

对于第一个样例的坐标最优移动顺序可以是:2→3→1,移动距离一共是3。
对于第二个样例的坐标最优移动顺序可以是:1→2→3,移动距离一共是2。
对于第三个样例的坐标最优移动顺序可以是:4→5→6→5,移动距离一共是3。

备注:

2≤n≤105,1≤m≤10,1≤p,pos[i]≤109

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
long long dp[2][100009],num[100009];
int n,m,t;
long long p;
int main()
{
   // freopen("cin.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%lld",&n,&m,&p);
        int pos=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&num[i]);
            if(num[i]<p) pos=i;
        }
        for(int i=0;i<2;i++)
            for(int j=0;j<100009;j++)
                dp[i][j]=2223372036854775807LL;
        for(int i=1;i<=n;i++)
        {
            if(i==pos) dp[1][i]=p-num[i];
            else if(i==pos+1) dp[1][i]=num[i]-p;
            //else dp[1][i]=0LL;
        }
        for(int i=2;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(j==1)
                    dp[i&1][j]=dp[(i+1)&1][j+1]+num[j+1]-num[j];
                else if(j==n)
                    dp[i&1][j]=dp[(i+1)&1][j-1]+num[j]-num[j-1];
                else
                    dp[i&1][j]=min(dp[(i+1)&1][j+1]+num[j+1]-num[j],dp[(i+1)&1][j-1]+num[j]-num[j-1]);
            }
        }
        long long len=2223372036854775807LL;
      //  printf("%lld\n",len);
        for(int i=1;i<=n;i++)
            len=min(len,dp[m&1][i]);
        printf("%lld\n",len);
    }
    return 0;
}



看题解发现有更简单的

可以想象的是如果 m 足够大,codeJan 最后肯定会选择在相邻的两个城市来回走。所以可
以枚举两个相邻的城市
(实际上应该是距离最小的两个城市)。并且直接” 奔向” 这两个城市的应该是最吼的!但是
还要考虑,可能先往后退到 一个城市,再” 奔向” 枚举的城市。
举个例子就明白了:n = 3,m = 10, p = 2,三个城市的位置是 1 10 14。
那么应该先退回到 1,然后再在 10 和 14 之间来回走。
时间复杂度:O(n)


题解说的少情况 看代码  不用两个点之间来回走的特判
#include <bits/stdc++.h>
using namespace std;
int T,n,m,p,a[200001];
int main()
{
    for(scanf("%d",&T);T;T--)
    {
        scanf("%d%d%d",&n,&m,&p);
        int pos=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]<p) pos=i;
        }
        long long ret=1000000000000000LL;
        for(int i=1;i<=n;i++)
        {
            long long ans=abs(p-a[i]);
            int step=max(pos-i+1,i-pos);
            long long luogan=min(a[i]-a[i-1],a[i+1]-a[i]);
            if(i==1) luogan=a[2]-a[1];
            if(i==n) luogan=a[n]-a[n-1];
            if(step<=m)
                ret=min(ret,ans+luogan*(m-step));
            if(step<m && pos!=0 && pos!=n)
            {
                if(a[i]>p)
                    ret=min(ret,ans+luogan*(m-step-1)+(p-a[pos])*2);
                else
                    ret=min(ret,ans+luogan*(m-step-1)+(a[pos+1]-p)*2);
            }
        }
        printf("%lld\n",ret);
    }
    return 0;
}