自动搬运

查看原文

来自洛谷，原作者为

	Error_Eric 终究还是意难平

搬运于2025-08-24 22:11:09，当前版本为作者最后更新于2023-11-18 10:35:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Statement

原题数据有误，现已更正

有 $12$ 种音符，在 $t_i$ 时刻需要演奏 $p_i$ 的音符（$1\le i\le N\le 100$）。

有 $D$ 个鼓，每个鼓对应一个音符，但是要求在任意时刻这几个鼓的音符严格上升。

求最大的 $q$，使得鼓手调节一个鼓的音符的时间为 $p$ 的条件下，有可能正确演奏这首歌曲。

Sol

比较套路。

注意到 $D$ 非常小但是 $N$ 不是非常小因此盲猜状压。

$f_{i,j}$ 表示演奏第 $i$ 个音符的时候鼓的状态为 $j$ 的情况下，最大的 $p$。如果无需调整则为 inf。

转移方程显然

$$f_{i,j}=\max\{f_{i-1,k}+\dfrac{t_i-t_{i-1}}{dif(j,k)}\} $$

其中 $dif(u,v)$ 表示 $u$ 鼓组和 $v$ 鼓组中有几个不同的。当然这里要特判 $u=v$ 的情况。

有一个细节是不能调整鼓的顺序。因此 $(1,3,4,5)\rightarrow(1,4,5,6)$ 其实需要调整三次而不是一次。

可以用各种奇怪的方式优化，例如预处理可能的状态，滚动掉第一维等等。不过我好像反向优化了一大堆东西，然而最终还是过了可见本题的时限是真的宽。

Code

#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include<cmath>
using namespace std;
typedef unordered_map<int,double> umap;
typedef unordered_map<int,vector<int>> umvi;
int n,d,t[105],p[105];
umap f[105]; // 其实完全没必要 umap，只是我当时懒得算状态数了
umvi digs; // 每个状态对应哪几个鼓
vector<int> with[15];
double ans=-1;
void tomax(double&o,double cmp){
    if(cmp>o) o=cmp;
}
void init(){
    for(int i=1;i<(1<<14);i++){
        vector<int> digits;
        for(int j=0;j<14&&digits.size()<=d*2;j++)
            if((i>>j)&1) digits.push_back(j);
        if(digits.size()==d) {
            for(int dx:digits)
                with[dx].push_back(i); 
                	// 预处理必须要有鼓 i 的状态
            digs[i]=digits;
        }
    }
}
double dif(int u,int v){ // 定义见上面的讲解
    int ans=0;
    for(int i=0;i<d;i++)
        ans+=(digs.at(u).at(i)!=digs.at(v).at(i));
    return ans;
}
const double inf=1e10;
int main(){
    //ios::sync_with_stdio(0),
    //cin.tie(0),cout.tie(0);
    cin>>n>>d,init();
    for(int i=1;i<=n;i++){
        cin>>t[i]>>p[i],--p[i];
        if(i==1){
            for(int now:with[p[i]])
                f[i][now]=inf;
            continue;
        }
        for(int now:with[p[i]]){
            f[i][now]=-1.0;
            for(int las:with[p[i-1]])
                if(now==las) // 特判前后状态相等
                    tomax(f[i][now],f[i-1][las]);
                else 
                    tomax(f[i][now],min(f[i-1][las],(t[i]-t[i-1])/dif(now,las)));
            if(i==n) 
                ans=max(ans,f[i][now]);
        }
    }
    if(ans>1e9) cout<<"0.00"<<endl;
    else printf("%.2f\n",ceil(100*ans)/100);
}