kdl 现状：P2460 [SDOI2007] 科比的比赛
fish_love_cat
·
·
题解
好好的一个题怎么全用爆搜肘过去啊，太不尊重牢大了这也。
我要为牢大正名所以我联合蓝色大鲸鱼把你们的爆搜全肘飞了（庆祝）！
容易发现 n 这么小所以有大量点是无用的。
于是我们可以贪心，按照获胜概率作为第一关键字，收益作为第二关键字排序。
容易发现无论怎么调整，每一次比赛我们都不可能选到这一行前 n 个以外的点。
于是我们对于 n 行每行保留 n 个点，于是 m 被降到了 O(n^2) 的量级。
考虑我们需要解决的问题是什么，本质上就是给你一个网格，每个网格有概率和收益，你要在上面放互不攻击的車，最大化其所在格子的概率乘积的基础上最大化收益之和。
一列一列的扫过去，直接对于行维护使用状态，暴力转移每个状态的最大概率以及这个概率下的最大收益。
暴力转移时间复杂度就是 $O(nm2^n)$ 的，因为 $m$ 经过压缩于是可以通过。
本题没有 spj，需要保留 12 位。
```cpp
#include<bits/stdc++.h>
using namespace std;
int v[100005];
bool use[100005];
struct fish{
int id,v;
long double x;
}a[100005];
bool cmp(fish x,fish y){
if(x.x==y.x)return x.v>y.v;
return x.x>y.x;
}
long double mp[15][100005];
long double dp[2][(1<<10)+5];
int rt[2][(1<<10)+5];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>v[i];
for(int op=1;op<=n;op++){
for(int i=1;i<=m;i++){
cin>>a[i].x;
a[i].id=i;
a[i].v=v[i];
mp[op][i]=a[i].x;
}
sort(a+1,a+1+m,cmp);
for(int i=1;i<=n&&i<=m;i++)
use[a[i].id]=1;
}
int op=0;
dp[0][0]=1;
for(int i=1;i<=m;i++)
if(use[i]){
op^=1;
for(int j=0;j<(1<<n);j++)
dp[op][j]=dp[op^1][j],
rt[op][j]=rt[op^1][j];
for(int j=0;j<(1<<n);j++)
for(int k=0;k<n;k++)
if((1<<k)&j){
long double flc=dp[op^1][j^(1<<k)]*mp[k+1][i];
if(flc>dp[op][j])
rt[op][j]=rt[op^1][j^(1<<k)]+v[i],
dp[op][j]=flc;
else if(flc==dp[op][j]&&rt[op^1][j^(1<<k)]+v[i]>rt[op][j])
rt[op][j]=rt[op^1][j^(1<<k)]+v[i];
}
}
printf("%.12llf\n%d",dp[op][(1<<n)-1],rt[op][(1<<n)-1]);
return 0;
}
// kdl 现状
// 在压
// 用dp
// kdl 现状：在压用 dp
// 图片来源：xmyz 801 黑板
// kdl 现状：看一天文学名著
```