【DP】【尺取法】尺取法总结

Singercoder · 2020-01-15 12:16:00 · 个人记录

算法介绍

• 算法简介：尺取法，又名two pointers（双指针法），是一种简洁而有效的dp优化算法，常见于将时间复杂度O（n^2)的一般dp优化为O（n）。

• 适用条件：限制变量随着指针的单向移动，而呈单调变化。

• 实现细节：

  1. 申请两个指针p_1,p_2。

  2. 固定p_1，使p_2递增直至满足条件。

  3. 保持p_2不动，使p_1向右移动，回到2。

模板分析

Sum

• 题意：输入一个含有n个元素的单调不降数列。输出所有数对a_i,a_j(1 \le i < j \le n)，使得a_i+a_j=m。

• O(n^2)朴素算法：枚举i和j，使得a_i+a_j=m。

• O(n)时间优化：对于任意数对a_i,a_j，限制变量sum满足i或j向右移动时，sum单调不降。（尺取法适用条件） 因此i向右移动时，要使sum不变，j应向左移动，可用尺取法优化。

#include<cstdio>
using namespace std;
const int MAXN=100010;
int n,m;
int a[MAXN];
inline void read()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
}
int main()
{
    read();
    for(int i=1,j=n;i<=n;i++)//初始化j在最右，保证获取到第一个解 
    {
        while(j-1>i&&a[i]+a[j-1]>=m)j--;//i增大时j减小，预判是否满足条件 

        if(i<j&&a[i]+a[j]==m)//确认条件以防越界
        printf("%d %d\n",a[i],a[j]);
    }
    return 0;
}