"NOIP 시뮬레이션"선물【상태 압축】【기대 DP】
하천의 생일이 곧 다가온다.하천의 형식적인 남자친구인 계당은 하천에게 생일 선물을 사주려고 한다.상점 안에는 모두 하나의 선물이 있다.하천은 한 가지 선물을 받을 때마다 그에 상응하는 기쁨치 Wi(각 선물의 기쁨치는 중복 획득할 수 없음)를 받는다.매번 점원은 일정한 확률로 Pi(또는 선물을 내놓지 않음)에 따라 i종 선물을 꺼낸다.계당은 매번 점원이 내놓은 선물을 사들인다.모두가 알다시피 흰 털은 잘라도 검다.그래서 계당은 마지막 하천의 기쁨이 가능한 한 높기를 바란다.구하천의 마지막 가장 큰 기쁨치가 얼마인지, 하천이 이 기쁨치, 계당의 기대 구매 횟수를 구해보자.
Input
첫 번째 줄에는 N가지 선물이 있음을 나타내는 정수 N이 있다.다음 N행은 각 행에 실수 Pi와 정수 Wi를 하나씩 주어 i번째 선물이 꺼질 확률과 기쁨치를 얻을 수 있음을 나타낸다.
Output
첫 번째 줄의 정수는 얻을 수 있는 최대 기쁨치를 나타낸다.두 번째 줄에서 하나의 실수는 이 기쁨치를 얻는 기대 구매 횟수를 표시하고 소수 세 자리를 보류한다.
f[s] f[s] f[s]는 상태 ss의 물품을 샀다는 기대를 나타낸다. s′=s-3-2i, i∈s'=s-2^i, i∈s′=s-32i, i∈s
그래서 다음과 같다. f[s]=∑f[s′]∗p-3∑pf[s]=\rac{\sumf[s']*p-1}{\sump}f[s]=∑p∑f[s]p-1
#include
#include
#include
#include
#include
#define db double
#define sg string
#define ll long long
#define rel(i,x,y) for(ll i=(x);i=(y);i--)
#define res(i,x) for(ll i=head[x];i;i=nxt[i])
using namespace std;
const ll N=20;
const ll Inf=1e18;
const ll Mod=1e9+7;
const db Eps=1e-10;
ll n,ans,all;
db f[1< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
NKOJ1066 굶주린 젖소 [DP]문제 설명 John은 약간의 젖소를 키웠는데, 매일 저녁 젖소는 모두 먹이를 먹어야 한다.조건이 비교적 누추하기 때문에 반드시 모든 젖소가 음식을 먹을 수 있는 것은 아니다.젖소의 식사 방식은 다음과 같다. John...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
