程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> BZOJ 3450 Tyvj1952 Easy 期望DP

BZOJ 3450 Tyvj1952 Easy 期望DP

編輯:關於C++

題目大意:給定一個OX序列,一些點未確定,連續len長度的O會得到len^2的收益,求期望收益值

令f[i]為第i個點的期望收益值,l[i]為第i個點的期望長度

如果一個點是'O' 那麼l[i]=l[i-1]+1 f[i]=f[i-1]+(l[i]*2-1)

如果一個點是'X' 那麼l[i]=0 f[i]=f[i-1]

如果一個點是'?' 那麼l[i]=(l[i-1]+1)/2 f[i]=f[i-1]+(l[i]*2-1)

等等 好像有些問題- -

如果一個點長度為1那麼增加的收益顯然是(1*2-1) 長度為2那麼增加的收益顯然是(2*2-1)

可是如果長度為0那麼增加的收益是(0*2-1)麼?顯然不是

實際上如果長度為0那麼收益可以按照長度為0.5計算

那麼最後一個遞推式改成f[i]=f[i-1]+(l[i-1]+0.5)即可

#include 
#include 
#include 
#include 
#define M 300300
using namespace std;
int n;
char s[M];
double f[M],l[M];
//f[i]表示第i個點的期望得分
//l[i]表示第i個點的期望長度
int main()
{
	int i;
	cin>>n;
	scanf("%s",s+1);
	for(i=1;i<=n;i++)
	{
		switch(s[i])
		{
			case 'o':
				l[i]=l[i-1]+1;
				f[i]=f[i-1]+(l[i]+l[i]-1);
				break;
			case 'x':
				l[i]=0;
				f[i]=f[i-1];
				break;
			case '?':
				l[i]=(l[i-1]+1)/2.0;
				f[i]=f[i-1]+(l[i-1]+0.5);
				break;
		}
	}
	printf("%.4lf\n",f[n]);
	return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved