hdu 1203 I NEED A OFFER! (물문제, dp)

1376 단어
소기: 1A
사고방식: dp, dp[v]는 v만 달러가 일자리를 얻지 못할 확률을 나타낸다
dp[v] = min(dp[v], dp[v-a[i].v] * a[i].t (v∈(0,n], i∈[1,m])
a[i].제i학교가 필요로 하는 달러, a[i].t는 실패할 확률을 나타낸다
마지막 answer는 (1-min(dp[v]))(v∈[0,n]))
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define eps 10e-8

const int MAX_ = 10010;
const int N = 100010;
const int INF = 0x7fffffff;

struct node{
    int v;
    double t;
}a[MAX_];

double dp[MAX_];

int main(){
	int n, m;
	double k, ans;
	while(~scanf("%d%d",&n, &m), n||m){
        for(int i = 0; i < m; ++i){
            scanf("%d%lf",&a[i].v, &k);
            a[i].t = 1.0 - k;
        }
        for(int i = 0; i <= n; ++i){
        	dp[i] = 1;
        }
        for(int i = 0; i < m; ++i){
            for(int v = n; v >= a[i].v; --v){
                dp[v] = min(dp[v], dp[v-a[i].v] * a[i].t);
            }
        }
        ans = INF;
        for(int i = 0; i <= n; ++i){
        	ans = min(ans, dp[i]);
        }

        printf("%.1f%%
", (1.0 - ans)*100); } return 0; }

좋은 웹페이지 즐겨찾기