UVA - 348 Optimal Array Multiplication Sequence(프리미엄 매트릭스 연승)
사고방식: 최우선 매트릭스 곱셈 문제, 전형적인 동적 기획 문제.
이 문제의 하위 문제는 "Ai,Ai+1,......,Aj를 곱하기 위해 몇 번의 곱셈이 필요한가"입니다. 만약 dp(i,j)로 이 문제의 하위 문제의 값을 표시한다면,
상태 이동 방정식: dp(i, j) =min{dp(i, k) + dp(k+1, j) + row(i)*col(k)*col(j)}
row는 현재 행렬의 줄을 대표하고,col은 현재 행렬의 열을 대표한다.
총괄: dp[i][j]의 초기 조건을 잘 쓰지 못했기 때문에 결과적으로wa는 여러 번 고려를 하지 않았고 dp[i][j]를 0으로 초기화하면 된다고 생각했다.
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 15;
struct Matrix {
int row,col;
}mat[N];
int dp[N][N], path[N][N];
void print_path(int l,int r) {
if(l == r) {
printf("A%d",l+1);
return ;
}else {
printf("(");
print_path(l,path[l][r]);
printf(" x ");
print_path(path[l][r]+1,r);
printf(")");
}
}
int main() {
int n , cas = 1;
while(scanf("%d",&n) != EOF && n) {
for(int i = 0; i < n; i++) {
scanf("%d%d", &mat[i].row, &mat[i].col);
}
memset(dp,0,sizeof(dp));
memset(path,0,sizeof(path));
for(int len = 1; len < n; len++) { //
for(int i = 0; i < n - len; i++) { //
int j = i + len;
dp[i][j] = dp[i][i] + dp[i+1][j] + mat[i].row * mat[i].col * mat[j].col;
path[i][j] = i;
for(int k = i+1; k < j; k++) { //
int tmp = dp[i][k] + dp[k+1][j] + mat[i].row * mat[k].col * mat[j].col;
if(tmp < dp[i][j]) {
dp[i][j] = tmp;
path[i][j] = k;
}
}
}
}
printf("Case %d: ",cas++);
print_path(0,n-1);
printf("
");
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
CloudFirestore의 array를 사용해보기CloudFirestore의 array를 사용하고 있는 기사가 별로 발견되지 않았으므로, 비망록적으로 남겨 둔다. 기재할 것 CloudFirestore 필드의 배열 유형 사용 (이번에는 추가) 기재하지 않는 것 Fi...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
