题解 P5475 [CCO2015] 定音鼓手
Error_Eric
·
·
题解
Statement
原题数据有误，现已更正
有 12 种音符，在 t_i 时刻需要演奏 p_i 的音符（1\le i\le N\le 100）。
有 D 个鼓，每个鼓对应一个音符，但是要求在任意时刻这几个鼓的音符严格上升。
求最大的 q，使得鼓手调节一个鼓的音符的时间为 p 的条件下，有可能正确演奏这首歌曲。
Sol
比较套路。
注意到 D 非常小但是 N 不是非常小因此盲猜状压。
转移方程显然
$$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
```cpp
#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);
}
```