题意: 不概括了..太长了..
额第一次做这种问题 算是概率dp吗?
保存前缀项中第一个和最后一个的概率 然后每添加新的一项 就解除前缀和第一项和最后一项的关系 并添加新的一项和保存的两项的关系
这里关系指的是两者相邻会产生的额外收入(其中一个满足条件就能得到 因此公式是 2000 * (rate[a] * rate[b] + rate[a] * ( 1 - rate[b]) + rate[b] * (1 - rate[a]))
至于一开始为什么老是调不过去呢..我发现添加第三项的时候前两项是不用解除关系的...
啊啊啊啊这题我敲了大半个小时敲得都烦死了= = 不过交上去直接Pretest Pass了
代码稍显冗长.. 凑和着看吧..
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 0x3f3f3f3f
#define mem(str,x) memset(str,(x),sizeof(str))
#define STOP puts("Pause");
using namespace std;
typedef long long LL; int main()
{
int n, p;
int l, r;
double rate[], ans = ;
scanf("%d%d", &n, &p);
scanf("%d%d", &l, &r);
if(l % p) rate[] = (double)(r / p - l / p) / (r - l + );
else rate[] = (double)(r / p - l / p + ) / (r - l + );
//printf("i = %d rate = %f\n", 1, rate[0]);
for(int i = ; i <= n; i++){
scanf("%d%d", &l, &r);
if(l % p) rate[] = (double)(r / p - l / p) / (r - l + );
else rate[] = (double)(r / p - l / p + ) / (r - l + );
if(i == ){
ans += (rate[] * rate[] + rate[] * ( - rate[]) + rate[] * ( - rate[])) * ;
rate[] = rate[];
}
else if (i == ){
ans += (rate[] * rate[] + rate[] * ( - rate[]) + rate[] * ( - rate[])) *
+ (rate[] * rate[] + rate[] * ( - rate[]) + rate[] * ( - rate[])) * ;
rate[] = rate[];
}
else{
ans += (rate[] * rate[] + rate[] * ( - rate[]) + rate[] * ( - rate[])) *
+ (rate[] * rate[] + rate[] * ( - rate[]) + rate[] * ( - rate[])) *
- (rate[] * rate[] + rate[] * ( - rate[]) + rate[] * ( - rate[])) * ;
rate[] = rate[];
}
//printf("i = %d rate = %f ans = %f\n", i, rate[2], ans);
}
printf("%f\n", ans);
return ;
}