poj 3014

1375 단어 2010
제목: m개의 케이크를 n개의 접시에 넣는 방안 수를 구하세요.
dp의 상태는 정말 생각나지 않는다. 남의 문제풀이를 보고 쓴 것이다.
상태 dp[i][j]는 j개의 케이크를 i개의 접시에 넣는 방안의 수를 나타낸다.
세 가지 토론:
1.i>j, 분명히 시간이 있을 거야. 그러면 dp[i-1][j]와 똑같아. 바로 i-1개의 접시에 j개의 케이크를 담았어. 네가 한 접시를 더 꺼내면 이 접시는 담지 않을 거야.
2.i==j 안에 빈 접시가 있으면 동상이고, 다 차면 가능성만 있고,
3. j>i가 시간이 있으면 동상, 꽉 차면 dp[i][j-i]종이 가능하다. 먼저 꽉 차게 하기 때문에 i개를 넣고 나머지 j-i개를 임의로 놓으면 이전의 상태가 된다.
if(i>j)dp[i][j]=dp[i-1][j];
if(i==j)dp[i][j]=dp[i-1][j]+1;
if(i<j)dp[i][j]=dp[i-1][j]+dp[i][j-i];

Run ID
User
Problem
Result
Memory
Time
Language
Code Length
Submit Time
9262319
201030720425
3014
Accepted
58828K
1954MS
C++
506B
2011-08-31 22:39:13
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int dp[4505][4505];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	dp[1][1]=1;dp[0][1]=0;dp[1][0]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(i>j)dp[i][j]=dp[i-1][j];
			if(i==j)dp[i][j]=dp[i-1][j]+1;
			if(i<j)dp[i][j]=dp[i-1][j]+dp[i][j-i];
			if(dp[i][j]>=1000000007)dp[i][j]-=1000000007;
		}		
		printf("%lld
",dp[n][m]); return 0; }

좋은 웹페이지 즐겨찾기