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

BZOJ 1076 SCOI2008 獎勵關 期望狀壓DP

編輯:關於C++

題目大意:給定k次彈出寶物的機會,每次隨機彈出n種寶物的機會,如果吃過這種寶物的所有前提寶物就可以吃這種寶物,求最優策略的期望得分

看到數據范圍果斷狀壓DP- - 不看數據范圍害死人- -

至於吃還是不吃 這是個問題

對於這種最優策略的期望DP 我們一般都是從後往前推

枚舉每次出現寶物 枚舉此時的狀態 枚舉寶物是哪種

如果當前的寶物可以吃 就在吃與不吃的後繼狀態中選擇最大值加到當前狀態上

如果當前的寶物不能吃 只能選擇不吃的後繼狀態加到當前狀態上

最後輸出f[1][0]就是答案

#include 
#include 
#include 
#include 
using namespace std;
int k,n,score[20],pre[20];
double f[110][1<<15];
int main()
{
	int i,j,x;
	cin>>k>>n;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&score[i]);
		while(scanf("%d",&x),x)
			pre[i]|=1<

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