三维dp&codeforce 369_2_C

标签： dp

---

codeforce 369_2_C

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<algorithm>

using namespace std;

#define ll long long

const ll INF = (ll)1e18;

const int N = 108;

ll dp[N][N][N];

int init[N];

ll cost[N][N];

int main()

{

	int n,m,c;

	while(~scanf("%d%d%d",&n,&m,&c))

	{

		for(int i = 1; i <= n; i++)

		{

			scanf("%d",&init[i]);

		}

		for(int i = 1; i <= n; i++)

		{

			for(int j = 1; j <= m; j++)

			{

				scanf("%I64d",&cost[i][j]);

			}

		}

		for(int i = 0; i <= n; i++)

			for(int j = 0; j <= m; j++)

				for(int k = 0; k <= c; k++)

					dp[i][j][k] = INF;

		if(init[1]==0)

		{

			for(int i = 1; i <= m; i++)

			{

				dp[1][i][1] = cost[1][i];

			}

		}

		else dp[1][init[1]][1] = 0;

		for(int i = 2; i <= n; i++)

		{

			for(int j = 1; j <= m; j++)

			{

				for(int k = 1; k <= c; k++)

				{

					if(init[i]!=0)

					{

						if(j!=init[i]) {

							dp[i][j][k] = INF;

							continue;

						}

						else {

							for(int u = 1; u <= m; u++)

							{

								if(u==j) dp[i][j][k] = min(dp[i-1][u][k],dp[i][u][k]);

								else if(u!=j) {

									dp[i][j][k] = min(dp[i][j][k],dp[i-1][u][k-1]);

								}

							}

						}

					}

					else if(init[i]==0)

					{

						for(int u = 1; u <= m; u++)

						{

							if(u==j){

								dp[i][j][k] = min(dp[i-1][j][k] + cost[i][j],dp[i][j][k]);

							}

							else if(u!=j)

							{

								dp[i][j][k] = min(dp[i-1][u][k-1] + cost[i][j],dp[i][j][k]);

							}

						}

					}

				}

			}

		}

		ll ans = INF;

		for(int i = 1; i <= m; i++)

		{

			ans = min(dp[n][i][c],ans);

		}

		if(ans==INF)

			puts("-1");

		else printf("%I64d\n",ans);

	}

	return 0;

}