UVa 10304. Optimal Binary Search Tree
제목이 비교적 간단해서 단번에 상태와 전이 방정식을 알아차렸다.
기억화 검색을 하기 시작했는데 처음에는 모든 임의의 두 수 사이의 수를 모두 구해서 저장할 생각을 하지 못했고 dp를 할 때마다 한 번씩 구했는데 결과가 제출된 후에 6.952s를 썼어요. 정말 느려 죽겠어요.그리고 dp에 들어가기 전에 한 개의 수조로 저장해야 한다고 생각했다. 이렇게 하면 좀 빠르고 중복 계산을 하지 않아도 된다.결국 6.144s를 썼다.(사실 이런 효과는 크지 않다. 기억화 검색으로도 중복 계산이 없기 때문에 효과가 좋지 않다) 이상하다. 왜 다른 사람들은 1s도 안 썼을까.
그리고 점차적인 사상으로 최적화를 하려고 했는데 나중에 2.276s를 사용했다. 비록 많이 빠르지만 1s를 들어갈 수 없다. 할 수 없다. 능력이 제한되어 최적화할 수 없다.
기억 검색:
#include <iostream>
#include <cstdio>
#include <string.h>
#include <cstring>
using namespace std;
int d[255][255];
int sum[255][255];
int n, fe[255];
int dp( int a, int b)
{
if( d[a][b]!=-1)
return d[a][b];
if( a==b )
return d[a][b] =0;
int i;
d[a][b]= dp( a+1, b) +sum[a][b]-fe[a];
if( dp( a,b-1) +sum[a][b]-fe[b]< d[a][b] )
d[a][b] =dp( a, b-1) +sum[a][b]-fe[b];
for( i=a+1; i<=b-1; i++)
{
int tem =dp( a,i-1) +dp( i+1, b)+ sum[a][b]-fe[i];
if( tem <d[a][b] )
d[a][b]= tem;
}
return d[a][b];
}
int main()
{
while( scanf("%d", &n)!=EOF )
{
int i,j;
for( i=0; i<n; i++)
scanf("%d", &fe[i] );
memset( d, -1, sizeof( d));
memset( sum , 0, sizeof( sum));
for( i=0; i<n ;i++)
{
sum[i][i] =fe[i];
for( j=i+1; j<n; j++)
sum[ i][j] =sum[i][j-1] +fe[j];
}
printf("%d
", dp(0,n-1) );
}
return 0;
}
점진적:
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
const int maxn =255;
int w[maxn][maxn];
int cost[maxn][maxn];
int f[maxn];
int main()
{
int n;
int i, j,k;
while(scanf("%d", &n)==1)
{
memset(w,0,sizeof(w));
memset(cost,0,sizeof(cost));
for(i=1;i<=n;i++)
scanf("%d", &f[i]);
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
{
w[i][j]=w[i][j-1]+f[j];
}
} //¼ÆËãÀÛ¼ÆƵÂʺÍ
for(i=2;i<=n;i++)
{
for(j=i-1;j>=0;j--)
{
cost[j][i]=1000000000;
for( k=j;k<=i;k++)
{
if(cost[j][k-1]+cost[k+1][i]+w[j][i]-f[k]<cost[j][i])
{
cost[j][i]=cost[j][k-1]+cost[k+1][i]+w[j][i]-f[k];
}
}
}
}
printf("%d
", cost[1][n]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.