【Codeforces #142 Div1】Solutions

A、B、C 문제 풀이
　　
【D. Towers】
　　 http://www.cnblogs.com/Delostik/archive/2012/10/03/2710655.html
제목:n 개의 탑 이 있 습 니 다.매번 조작 할 때마다 i 개의 탑 과 제(i-1)자리 또는 제(i+1)자 리 를 합 칠 수 있 습 니 다.새 탑 높이 는 두 탑 높이 와 합 칠 수 있 습 니 다.최소 몇 번 조작 한 후에 탑 높이 의 서열 이 떨 어 지지 않 게 하 느 냐 고 물 었 다.
O(n^2)의 방법:f[i]는 앞의 i 탑 높이 를 낮 추 지 않 는 최소 조작 횟수 를 나타 낸다.h[i]는 f[i]작업 을 수행 하 는 전제 에서 i 탑(또는 조작 i 가 합 친 새 탑)의 최소 높이 를 나타 낸다.
　　　　 f[i]=min{f[j]},sum(j,i)>=h[j-1],0≤j≤i ； h[i]=sum(j,i)
사전 처리 접두사 와,매 거 i,j,완료.
그 안에 욕심 을 쓰 는 것 은 i 에서 가장 가 까 운 j 가 가장 좋 을 것 이다.....................................................................
어떤 사람 은 단조 로 운 대열 이 라 고 말한다.......................................................................

#include <iostream>

using namespace std;



int n,H,f[5010],sum[5010],h[5010];



int main(){

	cin>>n;

	for(int i=1;i<=n;i++){

		cin>>H;

		sum[i]=sum[i-1]+H;

	}

	for(int i=1;i<=n;i++)

		for(int j=i-1;j>=0;j--)

			if(sum[i]-sum[j]>=h[j]){

				f[i]=f[j]+i-j-1;

				h[i]=sum[i]-sum[j];

				break;

			}

	cout<<f[n]<<endl;

}

 
【E. Gifts】
　　 http://www.codeforces.com/contest/229/problem/D
제목:어떤 선물 은 같은 이름 을 가지 고 있 고,어떤 선물 은 같은 가격 을 가지 고 있 지만,다른 이름 을 가 질 수 있다.사람 이 선물 이름 을 부 르 면 그 이름 중 하 나 를 무 작위 로 받는다.n 개의 가장 큰 가 치 를 가 진 선물 을 받 을 확률 이 얼마나 되 냐 고 물 었 다.
"이름 이 같은 선물 은 가격 이 다르다"는 말 이 중요 하 다.우 리 는 하나의 가치 하한 선 minv 를 확정 합 니 다.그러면 모든 선물 에 두 가지 가 있 습 니 다.하 나 는 반드시 선택해 야 하 는(v[i]>minv)이 고 다른 하 나 는 가치 가 마침 minv 와 같 아서 그 중의 일 부 를 선택 할 수 있 습 니 다.그 말 은 이름 별 선물 중 최대 1 개 는'선택'이나'선택 하지 않 음'을 선택 할 수 있다 는 것 을 알려 준다.
그래서 우 리 는 두 번 째 종 류 를 골 라 서 단독으로 만 들 었 는데,그것들 을'선택 할 수 있 는 선물'이 라 고 불 렀 다.선택 가능 한 선물 개수 choose=n-cnct 개,cnct 는 minv 보다 가치 가 큰 선물 수량 임 을 알 수 있 습 니 다.
f[i][j]전 i 종 이름 을 나타 내 는 선물 중 j 개 를 선택 했다.num[i]는 i 개의 선물 개 수 를 나타 내 고,must[i]는 i 의 선물 중 필수 선물 개 수 를 나타 낸다.
이전:1.i 번 째 이름 의 선물 중 선택 할 수 있 는 선물 이 없다 면 f[i][j]=f[i-1][j]/C(must[i],num[i])
2.i 번 째 이름 의 선물 중 선택 할 수 있 는 선물 이 있다 면 t=(n-cnt-j)/choose 는 i 번 째 선물 중 선택 할 수 있 는 선물 을 선택 할 확률 을 나타 낸다.
　　　　f[i][j]=f[i-1][j]/C(must[i],num[i])*(1-t)     선물
　　　　f[i][j+1]=f[i-1][j]/C(must[i],num[i]+1)*t   선물

#include <iostream>

#include <vector>

#include <iomanip>

#include <algorithm>

#define mn 1010

using namespace std;



vector<int> v[mn];

int n,m,x,minv,choose,cnt,tot,a[mn],must[mn],num[mn];

double C[mn][mn],f[mn][mn],tmp;

bool prob[mn];



int main(){

	for(int i=0;i<=1000;i++){

		C[i][0]=1;

		for(int j=1;j<=i;j++)

			C[i][j]=C[i-1][j]+C[i-1][j-1];

	}

	cin>>n>>m;

	for(int i=1;i<=m;i++){

		cin>>num[i];

		for(int j=1;j<=num[i];j++){

			cin>>x;

			v[i].push_back(x);

			a[++tot]=x;

		}

	}

	sort(a+1,a+1+tot);

	minv=a[tot-n];

	for(int i=1;i<=m;i++){

		for(int j=0;j<v[i].size();j++)

			if(v[i][j]>minv) cnt++,must[i]++;

			else if(v[i][j]==minv) prob[i]=true;

		choose+=prob[i];

	}

	f[0][0]=1;

	for(int i=1;i<=m;i++){

		for(int j=0;j<=n-cnt;j++)

			if(!prob[i]) f[i][j]=f[i-1][j]/C[num[i]][must[i]];

			else{

				tmp=(double)(n-cnt-j)/choose;

				f[i][j]+=f[i-1][j]/C[num[i]][must[i]]*(1-tmp);

				f[i][j+1]+=f[i-1][j]/C[num[i]][must[i]+1]*tmp;

			}

		choose-=prob[i];

	}

	cout<<fixed<<setprecision(10)<<f[m][n-cnt]<<endl;

}