/ Vijos / 讨论 / 题解 /

晴天小猪历险记之Hill题解

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define INF 0x7ffffabc
#define MAXN 1007
using namespace std;
void Read(int &p)
{
p=0;
int f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
p=p*10+c-'0',c=getchar();
p*=f;
}
int N,mp[MAXN][MAXN],dp[MAXN][MAXN];
void debug()
{
for(int i=1;i<=N;i++,putchar('\n'))
for(int j=1;j<=i;j++)
if(dp[i][j])printf("%d ",dp[i][j]);
}
int main()
{
Read(N);
for(int i=1;i<=N;i++)
for(int j=1;j<=i;j++)
Read(mp[i][j]);
dp[1][1]=mp[1][1];
for(int i=2;i<=N;i++)
{
for(int j=2;j<i;j++)
dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+mp[i][j];
dp[i][1]=min(dp[i-1][1],dp[i-1][i-1])+mp[i][1];
dp[i][i]=min(dp[i-1][i-1],dp[i-1][1])+mp[i][i];
for(int t=1;t<=2;t++)
{
for(int j=i-1;j>=1;j--)
dp[i][j]=min(dp[i][j],dp[i][j+1]+mp[i][j]);
dp[i][i]=min(dp[i][i],dp[i][1]+mp[i][i]);

for(int j=2;j<=i;j++)
dp[i][j]=min(dp[i][j],dp[i][j-1]+mp[i][j]);
dp[i][1]=min(dp[i][1],dp[i][i]+mp[i][1]);
}
}
printf("%d\n",dp[N][1]);
return 0;
}

0 条评论

目前还没有评论...