hdu 4906 Our happy ending

1809 단어 dp

제목: n개의 수를 선택하여 하나의 집합을 구성해야 한다. 각 수의 범위는 0~L이다. 집합에서 몇 개의 수를 선택하여 k를 구할 수 있고 이런 집합의 방안 수를 구해야 한다.
사고방식: 구화와 같은 k에 영향을 미치는 것은 1~k에 불과하고 다른 수는 선택해도 사용하지 않기 때문에 dp[i]로 상태가 i인 상황에서 얻을 수 있는 방안 수를 나타낸다.i는 현재 1~k의 k개수를 얻을 수 있는지, dp가 n회 진행하면 최종 결과를 얻을 수 있음을 나타낸다.dp시 선택한 수(1~min(k,L)를 매거한 다음에 얻을 수 있는 새로운 수와 원래의 상태를 합치거나 마지막으로 k를 얻을 수 있는 모든 상태의 값을 합치면 됩니다~
코드:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int mod=1000000000+7;
int dp[1<<20];
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k,L;
        scanf("%d%d%d",&n,&k,&L);
        ll ex=1;
        if(L>k) ex+=L-k;
        L=min(L,k);
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        int msk=(1<=0;--j)
            {
                int val=dp[j],state;
                if(dp[j]==0) continue;
                dp[j]=0;
                for(int x=1;x<=L;++x)
                {
                    state=j|((j<=mod) dp[state]-=mod;
                }
                dp[j]+=ex*val%mod;
                if(dp[j]>=mod) dp[j]-=mod;
            }
        }
        int ans=0;
        for(int i=0;i=mod) ans-=mod;
            }
        printf("%d
",ans);
    }
    return 0;
}

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

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

【경쟁 프로 전형적인 90문】008의 해설(python)

의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...

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

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

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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