贴代码—CF230 DIV1 B

#include<math.h>
#include<algorithm>
#include<string.h>

using namespace std;
long long dp[100][4][4];
int cost[4][4];
int n;
long long dfs(int n,int a,int c)
{
    if (n==0) return 0;
    if (dp[n][a][c]!=-1) return dp[n][a][c];

    int b=6-a-c;
    long long ans1=dfs(n-1,a,b)+cost[a][c]+dfs(n-1,b,c);
    long long ans2=dfs(n-1,a,c)+cost[a][b]+dfs(n-1,c,a)+cost[b][c]+dfs(n-1,a,c);
    dp[n][a][c]=min(ans1,ans2);
    return dp[n][a][c];
}
int main()
{
    memset(dp,-1,sizeof(dp));
    for (int i=1;i<=3;i++)
    for (int j=1;j<=3;j++)
    cin>>cost[i][j];
    cin>>n;
    cout<<dfs(n,1,3)<<endl;
    return 0;