hdu5569 BestCoder Round #63 (div.2)
행렬을 하나 드릴게요. 왼쪽 상단에서 오른쪽 하단까지 가는 비용을 요구합니다. a[1]*a[2]+a[3]*a[4]+......+a[2n-1]*a[2n]
아이디어:
과연 슬기롭지 못하여, 스스로 방법을 강구했다.
다음 그림과 같이 각 홀수 점에 대해 아래 각도가 있는 점은 3개의 값이 2인 점에 도달할 수 있으며 구체적인 그림을 그리면 알 수 있다.
그래서 우리는 유사한 dp 방법으로 각 점의 홀수점이 가장 좋은 것을 찾아내고 경계를 주의하면 된다
1 1 1 2
1 1 2 1
1 2 1 1
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long ll;
ll a[1005][1005];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m) != EOF)
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
scanf("%I64d",&a[i][j]);
}
a[1][2] *= a[1][1];
a[2][1] *= a[1][1];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if((i+j)%2)
{
int t1,t2,t3;
t1 = t2 = t3 = inf;
if(j > 2)
t1 = a[i][j-2]+a[i][j]*a[i][j-1];
if(i > 1 && j > 1)
t2 = a[i-1][j-1]+min(a[i][j]*a[i-1][j],a[i][j]*a[i][j-1]);
if(i > 2)
t3 = a[i-2][j]+a[i-1][j]*a[i][j];
t1 = min(t1,t2);
t1 = min(t1,t3);
if(t1 >= inf)
continue;
a[i][j] = t1;
}
}
printf("%I64d
",a[n][m]);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
