医院里的井

这是一个大家听过无数遍的笑话:某日,精神病院院长发现一患者蹲在井边,看着井里,一个劲地数:“13,13,13…”。院长迷惑不解,便走到该患者旁边,想看看井里到底有什么。没想到刚到井边,该患者便一把拉住院长,顺手将院长掷入井中,随后继续边看井内,边数着:“14,14,14…”

但是,怎么才能让这名患者的快乐值最大呢?假设这名患者之前丢的人的身高为k_i,现在丢的人的身高为k_i+1,患者需要的花费为。

    \[          |({k_i})^2 - ({k_{i+1}})^2| \]

患者只能按顺序丢人,但每次它可以将丢的人身高弄短。至于怎么弄短的就不用多去思考。但弄短成x的花费为(k_i-x)*m。怎样能让患者把所有人都丢完后花费最小?
其实很简单,单调队列就行了


#include<iostream>
#include<string>
#include<stdio.h>
#include<memory.h>
using namespace std;
#define inf 0xfffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b

int dp[2][101];
int q[101];
int head,tail,cur,ans;

int main()
{
    int n,m,x,i,j;
    scanf("%d%d",&n,&m);//n个人,m是职位变化参数
    scanf("%d",&x);
    cur = 0;
    for(int i=0;i<=x;i++)
        dp[cur][i] = (x-i)*m;// 10 9 .... 0 inf,代表这个人变成这个身高需要多少钱
    for(int i=x+1;i<=50;i++)
        dp[cur][i] = inf;
    for(i=1;i<n;i++)
    {
        scanf("%d",&x);
        cur = 1 - cur;
        head = tail = 0;
        //前一个人高,但自己可以变矮
        for(j = 0;j <= 50 ;j++)
        {
            ans = dp[1-cur][j]-j*j;//10+0 9+1 8+4 7+9 ... 0+100 inf inf,也就是说,当前一个人身高10时花费最少
            while(head < tail && q[tail-1] > ans)
                tail--;
            q[tail++] = ans;
            if(j > x)
                dp[cur][j] = inf;
            else
                dp[cur][j] = q[head]+j*j +(x-j)*m;//10+0-0+10 10-1+9 10-4+8 10-100+0 inf inf
        }
        //前一个人矮,但自己不可以变高
        head = tail = 0;
        for(j = 50;j >= 0;j--)
        {
            ans = dp[1-cur][j] + j*j;//inf inf .... 0-100 1-81 .... 8-4 9-1 10-0
            while(head < tail && q[tail-1] > ans)
                tail--;
            q[tail++] = ans;
            if(j <= x)
                dp[cur][j] = min(dp[cur][j],q[head]-j*j+(x-j)*m);//
        }
    }
    int real = inf;
    for(int i = 0;i <= 50;i++)
        real = min(real,dp[cur][i]);
    printf("%d\n",real);

    return 0;
}

Leave a Reply