HDU4248【DP】
n종의 돌이 있는데 각각의 돌이 a[i]개가 있다. 그리고 조합을 해서 몇 종의 조합이 있는지 물어보자.
사고방식: 이런 문제는 배열 조합 지식과 함께 매우 번거롭다. 이미 여러 문제를 풀었다. 마치 배열 조합의 자세인 것 같지만 결국은 일종의 추이, 즉DP이다. 그리고 비교적 뚜렷한 것은 기본적으로 이런 수의 수량급은 100/1000과 같다.DP는 일리가 있다.
이 문항:
pp[i][j]는 전 i더미의 돌의 구성 길이가 j의 직렬인 방안수를 나타낸다.
k는 제i더미가 j에 대한 사용량을 대표하고num은 현재 구성된 길이이다.
그리고 상태 이동은 dp[i, j]+=dp[i-1, j-k]*C[k,num]이다.
예처리 조합수, 조합의 성질을 이용: C(n+1,i)=C(n,i)+C(n,i-1);
마지막으로 모든 길이의 가능성의 종류를 더해주세요.
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
//dp[i][j] i j ；
const int N=1e4+10;
const LL mod=1e9+7;
//int num[N];
int num;
LL dp[110][N];
LL C[N][110];
void init()
{
C[0][0]=1;
for(int i=1;i 전재 대상:https://www.cnblogs.com/keyboarder-zsq/p/6216797.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
