UVA10616 - Divisible Group Sums(dp)
제목 링크
제목의 대의: N개수, m개수를 선택하여 더하기와MOD를 정제할 수 있는 몇 가지 선택 방식이 있는지 물어본다.
문제풀이 사고방식: 1부터 N수까지 과거를 선택하면 개수에 따라 선택할 수 있고 안 선택할 수 있다. 그리고 (num+d)%MOD =num%MOD +d%MOD를 선택할 수 있기 때문에 이렇게 할 수 있다. 마지막으로 나머지가 0이라고 판단할 수 있다.구덩이는 이 문제의 N 개수에 마이너스가 있고, 마이너스 모드(num% MOD + MOD)% MOD.이 문제는 선택의 수 m의 증가 횟수를 제어하지 못해서 레가 오랫동안 걸려서 정말 어이가 없어서 죽을 지경이다...
코드:
#include <cstdio>
#include <cstring>
typedef long long ll;
const int maxn = 205;
const int maxm = 15;
const int maxd = 25;
int N, Q, MOD, M;
int num[maxn], tmp[maxn];
ll f[maxn][maxm][maxd];
void init () {
for (int i = 0; i < N; i++)
scanf ("%d", &num[i]);
}
ll dp (int n, int m, int d) {
ll& ans = f[n][m][d];
if (ans != -1)
return ans;
if (n == N) {
if (m == M && d == 0)
return ans = 1;
return ans = 0;
}
ans = 0;
if (m < M)
ans += dp(n + 1, m + 1, (d + tmp[n]) % MOD);
ans += dp(n + 1, m, d);
return ans;
}
int main () {
int cas = 0;
while (scanf ("%d%d", &N, &Q) && (N || Q)) {
init();
printf ("SET %d:
", ++cas);
for (int i = 0; i < Q; i++) {
scanf ("%d%d", &MOD, &M);
memset (f, -1, sizeof (f));
for (int j = 0; j < N; j++)
tmp[j] = (num[j] % MOD + MOD) % MOD;
printf ("QUERY %d: %lld
", i + 1, dp(0, 0, 0));
}
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
