Petrozavodsk Summer 2017 JOI TST 2012 Selection | Kangaroo

G: Kangaroo
제목의 대의.
n(1≤n≤300)n(1≤n≤300)마리의 캥거루가 있는데, 각 캥거루의 크기는aiai이고, 자루의 크기는bibi이다.캥거루 캥거루는 한 마리까지 담을 수 있으며, 캥거루의 크기가 자루의 크기보다 작다는 것을 만족시킨다.캥거루를 담을 수 있는 합법적인 방안은 캥거루 한 마리가 다른 캥거루의 주머니에 들어갈 수 없다는 것을 가리킨다.캥거루를 담는 방법이 몇 가지냐고 물었다.
문제풀이
영fi,j,kfi,j,k는 전 ii의 큰 캥거루에 대해 jj조로 나뉘어 k개의 캥거루가 있는 자루는 반드시 캥거루(즉 캥거루가 있어 자루에 넣을 수 있지만 아직 넣지 않았다)를 의미한다.그럼 답은 ∑jfn, j, 0 ∑jfn, j, 0, 즉 k=0은 캥거루가 담을 수 없다는 뜻이다.
그러면 세 가지 상황이 있다.
4

i+1i+1마리의 캥거루를 새로 한 조로 배치하면fi,j,j,k→fi+1,j+1,alli+1,jfi,j,k→fi+1,j+1,a l li+1,j

i+1i+1마리의 캥거루를 kk개의 캥거루 주머니에 넣으면 kk종 선택,kfi,j,k→fi+1,j,k-31kfi,j,k→fi+1,j,k-1

i+1i+1마리의 캥거루를 kk개의 캥거루 이외의 주머니에 넣으면 알리, j-3-k a l i, j-3 k안, (alli+1, j-k)fi, j, k→fi+1, j, k(al l i+1, j-k)fi, j, k→fi+1, j, k

캥거루 몇 마리가 i를 담을 수 있는지 cnti c n t i로 표시합니다.alli, j a l i, j는 이전 i-3-1 i-3 1마리의 캥거루가 이미 j조에 몇 마리의 캥거루가 ii를 담을 수 있는지를 나타낸다. (어떤 캥거루는 이미 다른 캥거루를 담았기 때문에) 그러면 alli=cnti-3. (i-3-1 j) a l i=c n t i-3. (i-3 1-3 j)cntic n t i는 ii를 담을 수 있는 캥거루가 몇 마리인지를 표시하기 때문에 이미 다른 캥거루를 담은 캥거루는 반드시 i를 담을 수 있기 때문에 우리는 cntic n t i에서 이미 다른 캥거루를 담은 캥거루를 빼면 ii를 담을 수 있는 캥거루가 몇 마리 더 있는지 얻을 수 있다.
그럼 나머지는 간단해..

#include 
#include 
#include 
#include 
using namespace std;
#define FOR(i,j,k) for(i=j;i<=k;++i)
#define rep(i,j,k) for(i=j;i
typedef long long ll;
const ll MOD = 1e9 + 7;
const int N = 305;
int included[N];
ll dp[2][N][N];
pair<int, int> c[N];
int main()
{
    int i, j, k, n;
    scanf("%d", &n);

    FOR(i,1,n) scanf("%d%d", &c[i].first, &c[i].second);
    sort(c + 1, c + n + 1, greaterint, int>>());
    FOR(i,1,n) FOR(j,1,i)
        if (c[i].first < c[j].second)
            included[i]++;

    ll ans = 0;
    dp[0][0][0] = 1;
    FOR(i,1,n) 
    {
        int p = i & 1;
        memset(dp[p], 0, sizeof dp[p]);
        FOR(j,0,i)
        {
            int t = included[i] - (i - 1 - j);
            FOR(k,0,t)
            {
                (dp[p][j][k] += (dp[p ^ 1][j][k] * (t - k)) % MOD) %= MOD;
                if (k > 0) // 2.
                    (dp[p][j][k - 1] += (dp[p ^ 1][j][k] * k) % MOD) %= MOD;
                (dp[p][j + 1][t] += dp[p ^ 1][j][k]) %= MOD; // 1.
            }
        }
    }

    FOR(j,0,n)
        (ans += dp[n & 1][j][0]) %= MOD;
    printf("%lld
", ans);

    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

2019 진 황도 MUV LUV EXTRA (HDU 6740) 다음 배열 이해

제목: 어떻게 보면 무 서운 데 사실은 무한 순환 소수 상위 몇 명 을 주 고 순환 절 방안 을 선택 하 라 고 하 는 거 야. 시키다×순환 절 이 이미 나타 나 기 시작 한 부분의 길이 - b×순환 절의 길이 가 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Petrozavodsk Summer 2017 JOI TST 2012 Selection | Kangaroo | 동적 기획

좋은 웹페이지 즐겨찾기