wikioi-階段-普及一等-シーケンスdp-3027:線分被覆2
テーマ説明Description
数軸にはn本の線分があり、線分の両端は整数座標で、座標範囲は0~1000000で、線分ごとに1つの価値があります.n本の線分からいくつかの線分を選んで、これらの線分の2つがカバーされず(端点が重なることができます)、線分の価値の和が最大になります.
n<=1000
入力記述Input Description
最初の行は整数nで、何本のセグメントがあるかを示します.
次に、n行の各行の3つの整数、ai bi ciは、それぞれi番目の線分の左端点ai、右端点bi(左端点<右端点を保証する)、価値ciを表す.
出力記述Output Description
最大の価値を出力
サンプル入力Sample Input
3
1 2 1
2 3 2
1 3 4
サンプル出力Sample Output
4
データ範囲とヒントData Size&Hint
データ範囲
40%のデータに対して、n≦10;
100%のデータに対して、n≦1000;
0<=ai,bi<=1000000
0<=ci<=1000000
タイプ:dp難易度:1.5
題意:n個の線分を与えて、各線分の左右の端点(ai,bi)と価値ciを与えて、1組の2つの重ならない線分の価値の最大値を求めます.
解析:最長増分サブシーケンス問題と比較して類似しており、0-iから1つのセグメントセットが選択され、2つが重ならず、i番目のセグメントが最後の最大価値であることをdp[i]で表す.
繰返し方程式は、dp[i]=c[i]+max(dp[j])であり、0<=j=b[j]である.
最後にmax(dp[i])を求めることが求められる.
LISを用いた同様の最適化法,すなわちB[dp[i]=b[i]を用いることを考慮したが,この配列はdp[i]の値を得るセグメントセットを記録し,このセグメントセットが最も左の右境界b[i]をとることができる
毎回、a[i]以下の最大b[j]を検索する必要があるため、直接B[dp[i]]の2点で挿入位置を検索すれば、dp[i]を取得し、B[i]を更新することができる.
しかし、LISとは異なり、LISのB配列のdp[i]は最大増分長であり、この長さはnを超えず、本題のdp[i]の範囲はn*biであり、明らかにB配列が大きすぎて適用できないため、dp[iとb[i]を1つの]構造体に入れる方法が考えられる.しかし、valueが同じ(b[i]が同じ)項目が多く現れる可能性があります.これらの最大のa[i]以下のb[j]を見つけ、dp[i]が最大になるには、再二分検索が必要です.
コード(二分検索なし):
数軸にはn本の線分があり、線分の両端は整数座標で、座標範囲は0~1000000で、線分ごとに1つの価値があります.n本の線分からいくつかの線分を選んで、これらの線分の2つがカバーされず(端点が重なることができます)、線分の価値の和が最大になります.
n<=1000
入力記述Input Description
最初の行は整数nで、何本のセグメントがあるかを示します.
次に、n行の各行の3つの整数、ai bi ciは、それぞれi番目の線分の左端点ai、右端点bi(左端点<右端点を保証する)、価値ciを表す.
出力記述Output Description
最大の価値を出力
サンプル入力Sample Input
3
1 2 1
2 3 2
1 3 4
サンプル出力Sample Output
4
データ範囲とヒントData Size&Hint
データ範囲
40%のデータに対して、n≦10;
100%のデータに対して、n≦1000;
0<=ai,bi<=1000000
0<=ci<=1000000
タイプ:dp難易度:1.5
題意:n個の線分を与えて、各線分の左右の端点(ai,bi)と価値ciを与えて、1組の2つの重ならない線分の価値の最大値を求めます.
解析:最長増分サブシーケンス問題と比較して類似しており、0-iから1つのセグメントセットが選択され、2つが重ならず、i番目のセグメントが最後の最大価値であることをdp[i]で表す.
繰返し方程式は、dp[i]=c[i]+max(dp[j])であり、0<=j
最後にmax(dp[i])を求めることが求められる.
LISを用いた同様の最適化法,すなわちB[dp[i]=b[i]を用いることを考慮したが,この配列はdp[i]の値を得るセグメントセットを記録し,このセグメントセットが最も左の右境界b[i]をとることができる
毎回、a[i]以下の最大b[j]を検索する必要があるため、直接B[dp[i]]の2点で挿入位置を検索すれば、dp[i]を取得し、B[i]を更新することができる.
しかし、LISとは異なり、LISのB配列のdp[i]は最大増分長であり、この長さはnを超えず、本題のdp[i]の範囲はn*biであり、明らかにB配列が大きすぎて適用できないため、dp[iとb[i]を1つの]構造体に入れる方法が考えられる.しかし、valueが同じ(b[i]が同じ)項目が多く現れる可能性があります.これらの最大のa[i]以下のb[j]を見つけ、dp[i]が最大になるには、再二分検索が必要です.
コード(二分検索なし):
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
int n,a[1010][3],ans,dp[1010];
int cmp(const void *x, const void *y)
{
int *a = (int*)x, *b = (int*)y;
if(a[0]==b[0]) return a[1]-b[1];
return a[0]-b[0];
}
int main()
{
cin>>n;
for(int i=0; i<n; i++)
for(int j=0; j<3; j++)
cin>>a[i][j];
qsort(a,n,sizeof(int)*3,cmp);
ans = 0;
memset(dp,0,sizeof(dp));
dp[0] = a[0][2];
for(int i=1; i<n; i++)
{
int maxa = 0;
for(int j=0; j<i; j++)
{
if(a[i][0]>=a[j][1] && dp[j]>maxa)
{
maxa = dp[j];
}
}
dp[i] = maxa+a[i][2];
if(dp[i]>ans) ans = dp[i];
}
cout<<ans<<endl;
}