UVa 348 Optimal Array Multiplication Sequence(dp)
최우선 매트릭스 곱하기.
상태 이동 방정식: dp[x][y]=min(dp[x][y],DP(x,i)+DP(i+1,y)+node[x].x * node[i].y * node[y].y)
어려운 점은 인쇄에 있다. 나는 다른 사람의 코드를 보고서야 썼는데, 매우 정교하다.
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 10 + 2;
struct Node
{
int x,y;
};
Node node[MAX_N];
int dp[MAX_N][MAX_N];
int path[MAX_N][MAX_N];
int n;
int DP(int x,int y)
{
if(dp[x][y])
return dp[x][y];
for(int i = x;i < y;i++)
{
int temp = DP(x,i) + DP(i + 1,y) + node[x].x * node[i].y * node[y].y;
if(!dp[x][y] || temp < dp[x][y])
{
dp[x][y] = temp;
path[x][y] = i;
}
}
return dp[x][y];
}
void showPath(int x,int y)
{
if(x == y)
cout << "A" << x + 1;
else
{
cout << "(";
showPath(x,path[x][y]);
cout << " x ";
showPath(path[x][y] + 1,y);
cout << ")";
}
}
int main()
{
int num = 0;
while(cin >> n,n)
{
memset(dp,0,sizeof(dp));
memset(path,0,sizeof(path));
for(int i = 0;i < n;i++)
cin >> node[i].x >> node[i].y;
DP(0,n - 1);
cout << "Case " << ++num << ": ";;
showPath(0,n - 1);
cout << endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
