POJ 1695 Magazine Delivery G++ dp 没掌握
程序员文章站
2022-07-15 11:02:10
...
#include <iostream>
#include <cstring>
using namespace std;
//看博友分析 抄博有程序 dp 没掌握
int da[40][40];
int dp[40][40][40];//i表示此时状态所到达的最大城市编号,j,k为其余两车所在城市
int main()
{
int T;
cin>>T;
for(int o=0;o<T;o++)
{
int n;
cin>>n;
memset(da,0,sizeof(da));
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
cin>>da[i][j];
da[j][i]=da[i][j];
}
}
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp[n][i][j]=0;
}
}
for(int i=n-1;i>0;i--)
{
for(int j=1;j==1||j<i;j++)
{
for(int k=1;k==1||k<j;k++)
{
dp[i][j][k]=min(dp[i][j][k],dp[i+1][j][k]+da[i][i+1]);
dp[i][j][k]=min(dp[i][j][k],dp[i+1][i][k]+da[j][i+1]);
dp[i][j][k]=min(dp[i][j][k],dp[i+1][i][j]+da[k][i+1]);
}
}
}
cout<<dp[1][1][1]<<endl;
}
return 0;
}