首页 > 其他 > 详细

七彩线段 - 装压dp (牛客网)

时间:2018-10-15 23:59:11      阅读:254      评论:0      收藏:0      [点我收藏+]


题目描述
听说彩虹有七种颜色?
一维坐标轴上n条线段,每条线段左端点l,右端点r,颜色为c,从中选m种颜色的互不接触的线段,每种颜色可选多条,所选线段的总长度最长为多少?
输入描述:

第一行2个整数 n, m;
接下来n行,每行3个整数l, r, c。

输出描述:

一个整数,表示所选线段的最长的总长度;若选不了,输出-1;

示例1
输入
复制

4 2
1 3 1
4 5 1
5 8 2
7 9 3

输出
复制

5

示例2
输入
复制

4 3
1 3 1
4 5 1
5 8 2
7 9 3

输出
复制

-1

备注:

1 <= n <= 100000; 1 <= m <= 7;
1 <= l < r <= 1000000000; 1 <= c <= 7;

题意 : 在一维平面上给你 n 条线段,每条线段都有一个颜色,你可以在其中选出任意条线段,但任意两条均不能相交,且颜色数应恰好等于 m, 问你可以选取的最大长度是多少

思路分析 :观察发现颜色数 <= 7, 因此比较容易想到装压 dp,定义 dp[i][j] 表示到 i 条线段时,此时状态为 j 的最大长度

      显然根据这个可以去递推 dp[i][j|(1<<(arr[i].c-1))] = max(dp[i][j|(1<<(arr[i].c-1))], dp[pos][j]+arr[i].r-arr[i].l) 

      最后再数一下状态中 1 的个数刚好等于 m 的即可

代码示例 :

#define ll long long
const ll maxn = 2e5+5;

ll n, m;
struct node
{
    ll l, r, c;
    bool operator< (const node& v)const{
        return r < v.r;
    }
}arr[maxn];
vector<ll>ve;
ll dp[maxn][150];
ll bitnum[150];

void init(){
    bitnum[0] = 0;
    
    for(ll i = 1; i <= 130; i++) bitnum[i] = 1+bitnum[i&(i-1)];
}

void solve(){
    memset(dp, -1, sizeof(dp));  
    dp[0][0] = 0;
    ll ans = -1;
    
    for(ll i = 1; i <= n; i++){
        for(ll j = 0; j < 128; j++){ 
            dp[i][j] = max(dp[i-1][j], dp[i][j]);
            ll pos = upper_bound(ve.begin(), ve.end(), arr[i].l-1)-ve.begin();
            if(dp[pos][j] != -1) {
                dp[i][j|(1<<(arr[i].c-1))] = max(dp[i][j|(1<<(arr[i].c-1))], dp[pos][j]+arr[i].r-arr[i].l);
            }
            if (bitnum[j] == m) ans = max(ans, dp[i][j]);          
        }
    } 
    printf("%lld\n", ans);
}

int main() {
    init();
    
    cin >> n >> m;
    for(ll i = 1; i <= n; i++){
        scanf("%lld%lld%lld", &arr[i].l, &arr[i].r, &arr[i].c);
    }
    sort(arr+1, arr+1+n);
    for(ll i = 1; i <= n; i++) ve.push_back(arr[i].r);
    solve();
    
    return 0;
}

 

七彩线段 - 装压dp (牛客网)

原文:https://www.cnblogs.com/ccut-ry/p/9795475.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!