[openjude] 상자 와 작은 공의 4 (dp)

3143 단어 해제dp
제목 설명
전송 문
해제
이 문 제 는 Push Botton Lock 문제 와 비슷 하지만 제한 조건 을 추가 하면 상자 마다 적어도 k 개 를 넣 는 것 이다.그러면 두 번 째 string 은 그리 쉽 지 않 은 것 같 지만 데이터 범위 가 이렇게 작 으 면 O (n3) dp 를 직접 할 수 있 습 니 다.f (i, j) 를 설정 하면 i 개의 서로 다른 작은 공 을 j 개의 서로 다른 상자 에 넣 는 방안 수 를 나타 낸다. 그러면 f (i, j) = ＞ p = knf (i - p, j - 1) 는 8727 ° c (n - i + p, p) 이 고 그 중에서 c 는 조합 수 이다.당시 상태 와 같다.j - 1 개의 상자 에 i - p 개 를 넣 었 기 때문에 j 의 상 자 는 p 개 를 넣 고 n - i + p 개 를 선택 할 수 있 습 니 다.
코드
#include
#include
#include
using namespace std;
#define LL long long

int n,m,p;
LL c[20][20],f[20][20];

void clear()
{
    memset(f,0,sizeof(f));
}
int main()
{
    for (int i=0;i<=15;++i) c[i][0]=1;
    for (int i=1;i<=15;++i)
        for (int j=1;j<=15;++j)
            c[i][j]=c[i-1][j]+c[i-1][j-1];

    while (~scanf("%d%d%d",&n,&m,&p))
    {
        if (!n&&!m&&!p) break;
        clear();

        for (int i=p;i<=n;++i) f[i][1]=c[n][i];
        for (int i=p;i<=n;++i)
            for (int j=2;j<=m;++j)
            {
                for (int k=p;k<=i;++k)
                    if (i-k>=0)
                       f[i][j]+=f[i-k][j-1]*c[n-i+k][k];
            }
        printf("%lld
",f[n][m]);
    }
}
[낙 곡 P 1993] 작은 K 의 농장 [차분 제약]
블 루 브리지 컵 역대 시험 문제 호두 수량

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage