vva 1362 - Exploring Pyramids(구간 dp)
제목 연결: uva 1362 - Exploring Pyramids
제목 대의: 몇 종류의 다차수덕 전 서열이 있는지 묻는다. (이곳은 한 노드를 지나갈 때마다 이 노드의 값은 계산되고 거슬러 올라가도) 이 문자열을 만족시켜야 한다.
문제풀이 사고방식: dp[i][j]는 i에서 j까지의 위치를 몇 가지 다차원 나무로 표시할 수 있는지 나타낸다.전이 방정식: dp[i][j]=∑k=i+2jdp[i+1][k-1]∗dp[k][j].#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 305;
const ll MOD = 1e9;
char s[N];
ll dp[N][N];
ll solve (int x, int y) {
if (x == y)
return dp[x][y] = 1;
if (s[x] != s[y])
return dp[x][y] = 0;
ll& ans = dp[x][y];
if (ans >= 0)
return ans;
ans = 0;
for (int i = x+2; i <= y; i++) {
if (s[x] == s[i])
ans = (ans + solve(x+1, i-1) * solve(i, y))%MOD;
}
return ans;
}
int main () {
while (scanf("%s", s) == 1) {
memset(dp, -1, sizeof(dp));
printf("%lld
", solve(0, strlen(s)-1));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 305;
const ll MOD = 1e9;
char s[N];
ll dp[N][N];
ll solve (int x, int y) {
if (x == y)
return dp[x][y] = 1;
if (s[x] != s[y])
return dp[x][y] = 0;
ll& ans = dp[x][y];
if (ans >= 0)
return ans;
ans = 0;
for (int i = x+2; i <= y; i++) {
if (s[x] == s[i])
ans = (ans + solve(x+1, i-1) * solve(i, y))%MOD;
}
return ans;
}
int main () {
while (scanf("%s", s) == 1) {
memset(dp, -1, sizeof(dp));
printf("%lld
", solve(0, strlen(s)-1));
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
