Lightoj1084【DP啊DP】

题意：

给你n个人的位置，每个人最多移动k个单位，然后在某点>=3人可以抱团，问你这n个人最少抱团数，只要有一个n不能抱团输出-1；

思路：

感觉又是超级超级狗血。。。。

剪不断，理还乱。。。

现对人的位置拍个序

一开始想的是贪心，纯粹因为n1e5...，然后思路是对于每个位置搞一下，能延伸的最远距离，然后自然而然GG，位置没有办法。

后面去想对于每个人，向两边延伸最长距离，然后状态转移GG= =、

然后想前i个人，后面副参考窝大哥的博客，他是以第i个人为左边界，然后右边界的位置就是pos[i]+2*k，然后在数组里面找一下这个位置的人的位置，两个人区间人数>=3，然后取最小就好了;

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int>PII;

const double eps=1e-5;

const double pi=acos(-1.0);

const int INF=0x3f3f3f3f;

const int N=1e5+10;

int f[N],a[N];

int n,k;

int dfs(int i)

{

    if(f[i]!=-1)

        return f[i];

    if(i==n)

        return f[i]=0;

    int pos=upper_bound(a,a+n,a[i]+k)-a;

    f[i]=INF;

    for(int j=pos;j-i>=3;j--)

        f[i]=min(f[i],1+dfs(j));

    return f[i];

}

int main()

{

    int T,cas=1;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&k);

        for(int i=0;i<n;i++)

            scanf("%d",&a[i]);

        k*=2;

        sort(a,a+n);

        memset(f,-1,sizeof(f));

        dfs(0);

        if(f[0]<=0||f[0]==INF)

            f[0]=-1;

        printf("Case %d: %d\n",cas++,f[0]);

    }

    return 0;

}

巴特西

Lightoj1084【DP啊DP】

最新文章

热门文章