概率DP
Ryan_
2019-10-25 20:32:04
# 感性理解一下
```
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int INF=0x3f3f3f3f,maxn=1005;
int n;
struct node
{
int x,y,t;
double p;
bool operator<(const node &b)const
{
return t<b.t;
}
}a[maxn];
double dp[maxn];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d%d%lf",&a[i].x,&a[i].y,&a[i].t,&a[i].p);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)dp[i]=a[i].p;
double ans=dp[1];
for(int i=2;i<=n;i++)
{
for(int j=i-1;j>=1;j--)
{
ll D=(ll)(a[i].x-a[j].x)*(a[i].x-a[j].x)+(ll)(a[i].y-a[j].y)*(a[i].y-a[j].y);
ll T=(ll)(a[i].t-a[j].t)*(a[i].t-a[j].t);
if(D<=T)dp[i]=max(dp[i],dp[j]+a[i].p);
}
ans=max(ans,dp[i]);
}
printf("%.9f\n",ans);
return 0;
}
```
```
#include<bits/stdc++.h>
using namespace std;
int status,n;
double a[21][21],f[530000];
int main(){
cin>>n;
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
scanf("%lf",&a[i][j]);
}
}
status=(1<<n)-1;f[status]=1;
for (int i=status-1;i;i--){
int tot=0,tmp=i;
while (tmp){
tot+=(tmp&1);tmp>>=1;
//cout<<tot,exit(0);
}
for (int j=1;j<=n;j++){
if ((1<<j-1)&i) continue;
for (int k=1;k<=n;k++){
if (!((1<<k-1)&i)) continue;
f[i]+=(double)f[i|(1<<j-1)]*a[k][j]/(tot*(tot+1)/2);
}
}
}
for (int i=1;i<=n;i++){
printf("%.6lf ",f[1<<i-1]);
}
}
```