MYF

Codeforces 369C Coloring Trees

Posted on | In | | Visitors

题目链接

codeforces 369C

解题方法：DP

题目分析

题目大意

共有n棵树以及m种颜料，每棵树有一个数字c[i]如果c[i]==0表示这棵树需要染色，否则表示他已经有颜色，不能染色。现在规定这些树的美丽度为连续的区间数量，如2, 1, 1, 1, 3, 2, 2, 3, 1, 3可以分为{2}, {1, 1, 1}, {3}, {2, 2}, {3}, {1}, {3}，所以这些树的美丽度为7。现在希望能让这n棵树的美丽度为k，问最少需要花费的染料的数量

解析

写个检讨，不该手贱瞎判断的，Wrong answer on test 81，删了个条件就过了。

这题明显是用DP来做，状态也很好想，首先先构造两维，第一维表示前n棵树，第二维表示可以分为m，也就是说美丽度为m。当我们状态转移的时候，会发现第n棵树的DP值会跟随第n-1棵树的DP状态而变化，所以我们要再开一维去记录每次的最后一棵树的颜色。状态转移方程显而易见了，注意要分当前树有颜色和无颜色两种情况考虑。

这题wa也主要是wa在很多队友不明不白的wa在了B题然后开始讨论，自己心态一下也浮躁起来，想的不那么清楚，递推方程已经想出来了，但是边界条件没想清楚，其实DP方程已经可以解决所有不符合条件的情况了。做比赛看榜讨论害人害己啊！！想要足够强还有很长的路要走。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn=500+5;
const int mod=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-8;
int c[105];
ll p[105][105];
ll dp[105][105][105];
int mn[105]={1};
int main(){
    int n,m,k,pre=-1;
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1; i<=n; i++) {
        scanf("%d",&c[i]);
        mn[i] = mn[i-1];
        if (c[i]) {
            if (pre==-1) {
                pre = c[i];
            }
            else if (c[i]!=pre){
                mn[i]++;
                pre = c[i];
            }
        }
    }

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            scanf("%I64d",&p[i][j]);
        }
    }
    
    for (int i=1; i<=n; i++) {
        Memset(dp[i], INF);
    }
    
    int cnt = 0;
    for (int i=1; i<=n; i++) {
        if (c[i]) {
            for (int j=mn[i]; j<=i; j++) {
                dp[i][j][c[i]] = dp[i-1][j][c[i]];
                for (int q = 1; q<=m; q++) {
                    if (q!=c[i]) {
                        dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][q]);
                    }
                }
            }
        }
        else{
            for (int j=mn[i]; j<=i; j++) {  //共计j个线段
                for (int q = 1; q<=m; q++) {    //以颜色q结尾
                    dp[i][j][q] = dp[i-1][j][q];
                    for (int s = 1; s <= m; s++) {
                        if (s!=q) {
                            dp[i][j][q] = min(dp[i][j][q], dp[i-1][j-1][s]);
                        }
                    }
                    dp[i][j][q] += p[i][q];
                }
            }
        }
        
    }
    ll ans = INF;
    for (int i=1; i<=m; i++)
        ans = min(ans, dp[n][k][i]);
    
    if (ans == INF)
        puts("-1");
    else
        printf("%I64d\n",ans);
    return 0;
}