CF 82 D.Two out of Three

前言

全网唯一不同题解

设 \(f[i][j]\) 表示第 \(i\) 次选取留下来的数是 \(k\) 的最小花费

枚举前面的留下来的点 \(k\) 当前能留下的点只有 \((2*i),(2*i+1),k\) 中的一个，时间复杂度 \(O(n^2)\)

选取次数是 \(n/2\) 向上取整。因为最后什么点也不留下，\(a[n+1]=0\)，所以答案可以为 \(f[m][n+1](m=n/2向上取整)\)

另外我没有写记录路径，记录一下也挺简单

Code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define INF 0x3f3f3f3f
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 1007;
int n;
int a[N];
int f[N][N];
inline int Const(int x,int y) {
    return max(a[x], a[y]);
}
int main()
{
    n = read();
    for(int i=1;i<=n;++i)
        a[i] = read();
    memset(f, 0x3f, sizeof(f));
    f[1][1] = max(a[2],a[3]); f[1][2] = max(a[1],a[3]); f[1][3] = max(a[1],a[2]);
    int m = n&1 ? n/2+1 : n/2;
    for(int i=2;i<=m;++i) {
        int x = 2*i, y = 2*i+1; // i次选取的最后两个数 
        for(int k=1;k<x;++k) {  //枚举上一次留下的数 
            f[i][x] = min(f[i][x], f[i-1][k]+Const(y,k));
            f[i][y] = min(f[i][y], f[i-1][k]+Const(x,k));
            f[i][k] = min(f[i][k], f[i-1][k]+Const(x,y));
        }
    }
    int ans = f[m][n+1];
    printf("%d\n",ans);
    return 0;
}

update

加上路径记录版

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define INF 0x3f3f3f3f
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 1007;
int n;
int a[N];
int f[N][N];
struct operation {
    int x,y,pre;
}p[N][N];
inline int Const(int x,int y) {
    return max(a[x], a[y]);
}
void output(int now,int pos) {
    if(now == 0) return ;
    output(now-1,p[now][pos].pre);
    if(a[p[now][pos].x])    
        printf("%d ",p[now][pos].x);
    if(a[p[now][pos].y])
        printf("%d",p[now][pos].y);
    puts("");
}
int main()
{
    n = read();
    for(int i=1;i<=n;++i)
        a[i] = read();
    memset(f, 0x3f, sizeof(f));
    f[1][1] = max(a[2],a[3]); f[1][2] = max(a[1],a[3]); f[1][3] = max(a[1],a[2]);
    p[1][1] = (operation)<%2,3,0%>;
    p[1][2] = (operation)<%1,3,0%>;
    p[1][3] = (operation)<%1,2,0%>;
    int m = n&1 ? n/2+1 : n/2;
    for(int i=2;i<=m;++i) {
        int x = 2*i, y = 2*i+1; // i次选取的最后两个数 
        for(int k=1;k<x;++k) {  //枚举上一次留下的数 
            if(f[i-1][k]+Const(y,k) < f[i][x]) {
                f[i][x] = f[i-1][k]+Const(y,k);
                p[i][x] = (operation)<%k,y,k%>;
            }
            if(f[i-1][k]+Const(x,k) < f[i][y]) {
                f[i][y] = f[i-1][k]+Const(x,k);
                p[i][y] = (operation)<%k,x,k%>;
            }
            if(f[i-1][k]+Const(x,y) < f[i][k]) {
                f[i][k] = f[i-1][k]+Const(x,y);
                p[i][k] = (operation)<%x,y,k%>;
            }
            // f[i][x] = min(f[i][x], f[i-1][k]+Const(y,k));
            // f[i][y] = min(f[i][y], f[i-1][k]+Const(x,k));
            // f[i][k] = min(f[i][k], f[i-1][k]+Const(x,y));
        }
    }
    int ans = f[m][n+1];
    printf("%d\n",ans);
    output(m,n+1);
    return 0;
}