小さなファン度熊(尺取法)
「定規法」
この方法は二つの下付き(起点、終点)を利用して絶えず収縮して虫が伸びて這うようにして一番いい解を出します.このアルゴリズムは一回で答えが出るので、時間の複雑さはO(n)です.
このアルゴリズムの擬似コードと考え方を以下に示す.
この問題に対して、補足カードの個数は固定されています.定規法でまず一回を遍歴して、すべての区間を重複させないようにして、その後設立します.l=0、r=0、絶えずまたrを移動します.
停止し、最大値を更新し、lを右に移動し、lからl+1までの間に消費されたカードを返却し、上のステップを繰り返します.時間の複雑度はonです.
この方法は二つの下付き(起点、終点)を利用して絶えず収縮して虫が伸びて這うようにして一番いい解を出します.このアルゴリズムは一回で答えが出るので、時間の複雑さはO(n)です.
このアルゴリズムの擬似コードと考え方を以下に示す.
void worm_solve()
{
int res=MAX;
int s=0,t=0,sum=0;
for(;;)
{
while(tn)
{
res=0;
}
printf("%d
",res);
}
このアルゴリズムの難点は、どのようにして最適解を引き出すかということです.まず、条件を満たす終端tの位置を見つける必要があります.そのため、0から頭tを前によじ登らせます.尻尾sは動きません.条件を満たす時に止まると、このa[s]….a[t]のシーケンスに多くの「冗長値」があります.つまり、これらの値が除去された後も、シーケンスの総和はSより大きくなります.この時、虫の尻尾を移動させます.移動長を決めることができないので、毎回一つの単位だけ移動すればいいです.末尾が1になるたびに、sumから相応のインデント値を除去し、現在のシーケンスとSとの関係がどのように条件を満たすかを再度判断します.そうしないと、改めて虫の頭を前に進ませます.このように伸びて縮むと、虫のようにアルゴリズムが一番いい解を求めます.このアルゴリズムの適用のタイプは、いくつかの連続区間のカバー問題を解決することです.この問題に対して、補足カードの個数は固定されています.定規法でまず一回を遍歴して、すべての区間を重複させないようにして、その後設立します.l=0、r=0、絶えずまたrを移動します.
停止し、最大値を更新し、lを右に移動し、lからl+1までの間に消費されたカードを返却し、上のステップを繰り返します.時間の複雑度はonです.
#include
const int mod= 1e9+7;
typedef long long ll;
using namespace std;
const int maxn = 100005;
typedef pair P;
P p[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n,m;
while(cin>>n>>m)
{
for(int i=0;i>p[i].first>>p[i].second;
sort(p,p+n);
int temp=0;
for(int i=0;i0 && p[l+1].first - p[l].second-1+tmp <= m)
//
{
tmp+=p[l+1].first - p[l].second-1;
}
l++;
while(l>r)
r++;
}
cout<