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

题目描述
听说彩虹有七种颜色？
一维坐标轴上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

输出
复制

示例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 (牛客网)

最新文章

热门文章