글 읽기 - 행렬 곱셈문제 알고리즘 크누스최적화 질문입니다.

joseph415 5년 전 1

이 알고리즘 문제 파일합치기랑 똑같은거같아서

파일 합치기는 크누스최적화가 적용이 되었었는데

이번에도 똑같이 해봤는데 ㄱ
ㅔ속 틀렸습니다 떠서 질문드립니다.

혹시 크누스 알고리즘으로 풀수없나요??

답은 나오는데 바로 틀렸습ㄴ디다 뜨길래 질문드립ㄴ디ㅏ.

#include <iostream>
#include <climits>
using namespace std;

long long d[501][501];
int a[501][501];



struct metrix{
    long long x1;
    long long x2;
};

metrix m[501]={};

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    long long n;
    cin>>n;

    for(int i=1;i<n+1;i++){
        cin>>m[i].x1>>m[i].x2;
    }

    for(int i=1;i<n+1;i++){
        a[i-1][i]=i;
    }
 
    
    //크누스 알고리즘

    for(int i=2;i<=n;i++){
        for(int x=0;x+i<=n;x++){
            int y=x+i;

            d[x][y]=INT_MAX;

            for(int k=a[x][y-1];k<=a[x+1][y];k++){
                int ans=d[x][k]+d[k][y]+(m[x+1].x1*m[k].x2*m[y].x2);
                if(d[x][y]>ans){
                    d[x][y]=ans;
                    a[x][y]=k;
                }
            }
        }
    }
    cout<<d[0][n]<<"\n";

}