bzoj 1042 HAOI 2008 코인 쇼핑
7845 단어 2008
우선 제한이 없는 방안의 수를 dp로 낸다.
dp 할 때 주의 먼저 순환 1...4 번 더. 1 번.maxs 중복 방지.경계는 f[0] = 1입니다.이렇게 기초적인 가방은 다 까먹었어 = =
이어서 중복된 문제를 처리하고 원리를 용납하다
용척의 원리는 말하자면 매우 간단하지만, 예를 들어 이 문제와 같은 신기한 응용이 있다.
최종 답안 = 제한 없는 시나리오 - 한 가지 제한 초과 시나리오 + 두 가지 제한 초과 시나리오 - 세 가지 제한 초과 시나리오 + 네 가지 제한 초과 시나리오
ans = f[s] + f[s - c[i]*(d[i]+1)] - …… + f[s - c[1]*(d[1]+1)……]
왜 d[i]+1이죠?
적어도 d[i]+1개를 사용하고 나머지는 자유롭고 제한이 없는 방안수입니다.
위 코드:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100010
using namespace std;
int c[5], n, d[5], s;
long long f[N] = {0};
void make_f()
{
f[0] = 1;
for (int j = 1; j <= 4; ++j)
for (int i = c[j]; i <= N-10; ++i)
f[i] += f[i-c[j]];
}
long long getans()
{
long long ans = f[s];
for (int i = 1; i <= 4; ++i)
if (s - c[i]*(d[i]+1) >= 0)
ans -= f[s - c[i]*(d[i]+1)];
for (int i = 1; i <= 3; ++i)
for (int j = i+1; j <= 4; ++j)
if (s - c[i]*(d[i]+1) - c[j]*(d[j]+1) >= 0)
ans += f[s - c[i]*(d[i]+1) - c[j]*(d[j]+1)];
for (int i = 1; i <= 2; ++i)
for (int j = i+1; j <= 3; ++j)
for (int k = j+1; k <= 4; ++k)
if (s - c[i]*(d[i]+1) - c[j]*(d[j]+1) - c[k]*(d[k]+1) >= 0)
ans -= f[s - c[i]*(d[i]+1) - c[j]*(d[j]+1) - c[k]*(d[k]+1)];
if (s - c[1]*(d[1]+1) - c[2]*(d[2]+1) - c[3]*(d[3]+1) - c[4]*(d[4]+1) >= 0)
ans += f[s - c[1]*(d[1]+1) - c[2]*(d[2]+1) - c[3]*(d[3]+1) - c[4]*(d[4]+1)];
return ans;
}
int main()
{
for (int i = 1; i <= 4; ++i) scanf("%d", &c[i]);
make_f(); scanf("%d", &n);
while (n--)
{
for (int i = 1; i <= 4; ++i) scanf("%d", &d[i]);
scanf("%d", &s);
printf("%I64d
", getans());
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj 1042 HAOI 2008 코인 쇼핑이 문제의 사고방식은 신이다. 우선 제한이 없는 방안의 수를 dp로 낸다. dp 할 때 주의 먼저 순환 1...4 번 더. 1 번.maxs 중복 방지.경계는 f[0] = 1입니다.이렇게 기초적인 가방은 다 까먹었어 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.