POJ 1651 Multiplication Puzzle(구간 DP)
dp[i][j]로 구간[i,j]의 모든 숫자를 제거한 후의 가장 좋은 결과를 나타낸다.그러면 상태는 ans=min(ans, dp(i, k-1)+a[k]*a[i-1]*a[j+1]+dp(k+1, j)로 이동);이 상태의 이동은 구간 [i, j]에 대한 마지막 살k를 나타낸다.왜 이렇게 옮겨요?당신이 선택한 이 숫자는 좌우의 숫자가 그에 영향을 미칠 수 있기 때문에 교묘하게 이 영향을 없애고 문제를 하위 문제로 옮길 수 있다.마지막으로 k를 선택했으니 얻은 점수는 자연히 a[k]*a[i-1]*a[j+1]이다.
자세한 참고 코드:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<numeric>
#include<functional>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<cassert>
#include<complex>
#include<iomanip>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 205;
const int INF = 1000000000;
int T,n,kase=0,a[maxn],b[maxn],d[maxn][maxn];
int dp(int i, int j) {
if(i > j) return 0;
int& ans = d[i][j];
if(ans != -1) return ans;
ans = INF;
for(int k=i;k<=j;k++) ans = min(ans,dp(i,k-1)+a[k]*a[i-1]*a[j+1]+dp(k+1,j));
return ans;
}
int main() {
while(~scanf("%d",&n)) {
memset(d,-1,sizeof(d));
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
a[n+1] = b[n+1] = 1;
int ans = dp(2,n-1);
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
