CF82D Two out of Three 题解

· · 题解

\text{Difficulty : 2000}

解题思路：

动态规划。

设 f_{i,j} 表示考虑到第 i 次结账，其中第 j 个人被留了下来的最短时间。

然后考虑转移，对于每一种状态，留下来的那一个人有可能是之前的某一个人，也有可能是让之前的某一个人结账留下当前新加入的那两个人中的一个。

具体讨论每一种情况：

  1. 留下来的人是之前的某一个人。直接枚举这个人，结账的是当前的那两个人，也就是 f_{i,j}=f_{i-1,j}+\max(a_{2i},a_{2i+1})。

  2. 留下来的人是当前的某一个人。枚举之前没有结账的是哪一个人，结账的就是剩下的两个人。由于新加入的有两个，对称地有：f_{i,2i+t}=\min(f_{i-1,j}+\max(a_j,a_{2i+1-t}))。其中 t\in[0,1]，且 t\in Z。

可以将 a_{n+1} 设定为正无穷，这样如果 n 是偶数，最后的答案一定在 f_{\left\lfloor\frac{n}{2}\right\rfloor,n+1} 中，也就是一定会将一个不存在的 n+1 保留下来，让所以其它的进行结账。如果 n 是奇数，则需要枚举最后保留下来的那个顾客，单独结账。

注意本题还要求输出路径。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a[1005],f[1005][1005],fr[1005][1005],p[1005][1005][2],minx,mini,now;
int rec[1005][2];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    memset(f,63,sizeof(f));
    a[n+1]=1e9;f[0][1]=0;
    for(int i=1;i<=n/2;i++){
        for(int j=1;j<2*i;j++){
            if(f[i-1][j]+max(a[i*2],a[i*2+1])<f[i][j]){
                f[i][j]=f[i-1][j]+max(a[i*2],a[i*2+1]);
                fr[i][j]=j;
                p[i][j][0]=i*2;
                p[i][j][1]=i*2+1;
            }
            if(f[i][i*2]>f[i-1][j]+max(a[i*2+1],a[j])){
                f[i][i*2]=f[i-1][j]+max(a[i*2+1],a[j]);
                fr[i][i*2]=j;
                p[i][i*2][0]=j;
                p[i][i*2][1]=i*2+1;
            }
            if(f[i][i*2+1]>f[i-1][j]+max(a[i*2],a[j])){
                f[i][i*2+1]=f[i-1][j]+max(a[i*2],a[j]);
                fr[i][i*2+1]=j;
                p[i][i*2+1][0]=i*2;
                p[i][i*2+1][1]=j;
            }
        }
    }
    if(n%2==0){
        printf("%d\n",f[n/2][n+1]);
        int now=n+1;
        for(int i=n/2;i>=1;i--){
            rec[i][0]=min(p[i][now][0],p[i][now][1]);
            rec[i][1]=max(p[i][now][0],p[i][now][1]);
            now=fr[i][now];
        }
        for(int i=1;i<=n/2;i++)
        printf("%d %d\n",rec[i][0],rec[i][1]);
    }
    else{
        minx=2147483647;
        for(int i=1;i<=n;i++){
            if(f[n/2][i]+a[i]<minx){
                minx=a[i]+f[n/2][i];
                mini=i;
            }
        }
        printf("%d\n",minx);
        int now=mini;
        for(int i=n/2;i>=1;i--){
            rec[i][0]=min(p[i][now][0],p[i][now][1]);
            rec[i][1]=max(p[i][now][0],p[i][now][1]);
            now=fr[i][now];
        }
        for(int i=1;i<=n/2;i++)
        printf("%d %d\n",rec[i][0],rec[i][1]);
        printf("%d\n",mini);
    }
    return 0;
}