首页 > 代码库 > codeforces 711C dp

codeforces 711C dp

2024-08-12 15:23:56   216人阅读

一眼dp，但是这道题不知怎么搞遇到点小问题，又搞了搞才出来，就是给你一些颜色。这个点有颜色，不能图，反之可以。问形成k段连续颜色的最小花费。

纯纯的dp，不知道为什么就是有问题。。。终于借鉴了别人的A过了，后面再研究吧。

#include <cstdio>#include <cstring>#include <vector>#include <cmath>#include <stack>#include <cstdlib>#include <queue>#include <map>#include <iostream>#include <algorithm>#include <bits/stdc++.h>using namespace std;typedef long long LL;LL dp[110][110][110];LL p[210][210];LL a[110];LL inf=0x7f7f7f7f;int main(){    LL n,m,k;    scanf ("%I64d%I64d%I64d",&n,&m,&k);    for (LL i=1;i<=n;i++)    {        scanf ("%I64d",&a[i]);    }    for (LL i=1;i<=n;i++)    {        for (LL j=1;j<=m;j++)        {            scanf ("%I64d",&p[i][j]);        }    }    memset(dp,inf,sizeof(dp));    if (a[1])    {        dp[1][1][a[1]]=0;    }    else    {        for (LL i=1;i<=m;i++)        {            dp[1][1][i]=p[1][i];        }    }    for (LL i=2;i<=n;i++)    {        if (!a[i])        {            for (LL x=1;x<i;x++)            {                for (LL c=1;c<=m;c++)                {                    for (LL l=1;l<=m;l++)                    {                        if (l!=c)                        dp[i][x+1][c]=min(dp[i][x+1][c],dp[i-1][x][l]+p[i][c]);                        else dp[i][x][c]=min(dp[i][x][c],dp[i-1][x][l]+p[i][c]);                    }                }            }        }        else        {            for (LL x=1;x<i;x++)            {                for (LL l=1;l<=m;l++)                {                    if (l==a[i])                        dp[i][x][a[i]]=min(dp[i][x][a[i]],dp[i-1][x][a[i]]);                    else dp[i][x+1][a[i]]=min(dp[i][x+1][a[i]],dp[i-1][x][l]);                }            }        }    }    LL ans=inf;    for (LL i=1;i<=m;i++)    {        ans=min(dp[n][k][i],ans);    }    if (ans==inf) ans=-1;    printf ("%I64d\n",ans);    return 0;}

 

codeforces 711C dp


联系
我们