hdu 5396 Expression(구간 dp)
조합수를 곱해야 합니다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100;
const int mod = 1e9 + 7;
typedef long long ll;
int C[maxn + 5][maxn + 5], F[maxn + 5];
int N, dp[maxn + 5][maxn + 5];
char order[maxn + 5];
void init () {
for (int i = 0; i <= maxn; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++)
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
}
F[0] = 1;
for (int i = 1; i <= maxn; i++)
F[i] = 1LL * i * F[i-1] % mod;
}
int main () {
init ();
while (scanf("%d", &N) == 1) {
memset(dp, 0, sizeof(dp));
for (int i = 0; i < N; i++) scanf("%d", &dp[i][i]);
scanf("%*c");
gets(order);
N--;
for (int i = N-1; i >= 0; i--) {
for (int j = i + 1; j <= N; j++) {
int len = j - i - 1;
for (int k = i; k < j; k++) {
int l = k - i, r = j - k - 1;
ll ret = 0;
if (order[k] == '+') {
ret = (ret + 1LL * dp[i][k] * F[r]) % mod;
ret = (ret + 1LL * dp[k+1][j] * F[l]) % mod;
} else if (order[k] == '-') {
ret = (ret + 1LL * dp[i][k] * F[r]) % mod;
ret = ((ret - 1LL * dp[k+1][j] * F[l]) % mod + mod) % mod;
} else if (order[k] == '*')
ret = 1LL * dp[i][k] * dp[k+1][j] % mod;
dp[i][j] = (dp[i][j] + ret * C[len][l]) % mod;
}
//printf("%d %d: %d
", i, j, dp[i][j]);
}
}
printf("%d
", dp[0][N]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.