NOIP Dp基本套路大全

套路大全"/>

NOIP Dp基本套路大全

前言：

Dp，一直是困扰许（我）许（这）多（一）多（个）Oler（蒟蒻）的问题之一。而在看似毫无章法与固定解题模式的Dp题中，却实实在在有那么一些基本套路，帮助我们在求解Dp的过程中能给我们或多或少提（多）供（骗）一些思（水）路（分）。

持续更新中。。。求大佬指正orz。

---

正文:

---

基础套路：

P.S:（以下的状态转移方程只是最基础的，不含其他优化）

---

（1）最长公共子序列

题意
询问你两个字符串的最长公共子序列。

状态转移方程

    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(s1[i]==s2[j])f[i][j]=f[i-1][j-1]+1;else f[i][j]=max(f[i-1][j],f[i][j-1]);// 预处理: 无
// i: 枚举到的s1串的位置
// j: 枚举到的s2串的位置    
// 时间复杂度：N*M

例题
HDU 5495
HDU 1503

---

（2）最长不下降子序列

题意
询问你一个数列的最长不下降子序列
（拓展）：一个数列能拆城的最少的不下降子序列个数。

状态转移方程（？）

  for(int i=1;i<=n;i++){cin >> a[i];int left=1,right=ans;while(left<=right){int mid=(left+right)/2;if(a[i]<=num[mid])right=mid-1;elseleft=mid+1;}if(left>ans)  ans++;num[left]=a[i];}cout<<ans<<endl;return 0;
}// 二分+贪心，每次每次把同一位替换成更小的数。
// 时间复杂度：N*log(N)

    for(int i=1;i<=n;i++){for(int j=1;j<i;j++)if(a[i]<=a[j])dp[1][i] = max(dp[1][i],dp[1][j]+1);elsedp[2][i] = max(dp[2][i],dp[2][j]+1);ans1 = max(ans1,dp[1][i]);ans2 = max(ans2,dp[2][i]);          }// 预处理：dp[1,2][1~n]=1
// dp[1]-- i:当前枚举的第i个数字
// dp[2]-- i:当前枚举的第i个数字（拓展）
// 时间复杂度：N^2

例题
HDU 1257
HDU 1025

---

（3）最多不冲突区间（自己取的名）

题意
给你一系列的区间，询问你最多能安排多少区间，使他们的交集为空（不
发生冲突）。

状态转移方程

    for(int i=1;i<=n;i++){if(a[i].s>=pre)f[i]=f[i-1]+1,pre=a[i].t;else f[i]=f[i-1];}// 预处理: 将所有区间以结束时间为第一关键字从小到大排序。
// i: 枚举到第几个区间
// 时间复杂度：NP.S:事实上也可以贪心做。。。

例题
HDU 5495
HDU 1503

---

（4）最大连续区间和

题意
给你一个数列，询问你整个数列的最大区间和 或者 指定区间长度的最大区间和。

状态转移方程

//整个数列的最大区间和for(int i=1;i<=n;i++)
{last = max(0,last)+a[i];ans = max(ans,last);
}// i:枚举到的数在数列中的位置
// 时间复杂度：N

//整个数列的最大区间和
//前缀和版本（不算优化吧。。。）for ( int i = 1 ; i <= n ; i++ )
{ans = max(ans,sum[i]-minn);minn = min(minn,sum[i]);
}// i:枚举到的数在数列中的位置
// 时间复杂度：N

//指定区间长度K的最大值（区间长度小于等于K）
//单调队列优化for(i=1;i<=n;i++){while(tail>front&&sum[i-1]<sum[que[tail-1]])tail--;que[tail++]=i-1;while(tail>front&&i-que[front]>k)front++;if(ans<sum[i]-sum[que[front]]){ans=sum[i]-sum[que[front]];ans1=que[front]+1;ans2=i;}}// ans:最大和   ans1:区间起点  ans2:区间终点
// i:枚举到的数在数列中的位置 
// 时间复杂度：N

HDU 3415
HDU 1231

---

（5）矩阵前缀和优化（哈希优化）

题意
给你一个矩阵，询问你子矩阵中和为K的倍数的矩阵个数 或者 和为特定值的矩阵的个数

状态转移方程

//前缀和被特定值（q）整除的个数【正整数】 
hash[0]=1;
for(int i=1;i<m;i++)for(int j=i+1;j<=m;j++){for(int k=1;k<=n;k++)ans += hash[(sum[k][j]-sum[k][i]+q<<1)%q]++;for(int k=1;k<=n;k++)hash[(sum[k][j]-sum[k][i]+q<<1)%q]--;}// i,j：枚举 长/宽
// k：枚举 行数/列数
// 哈希存储前缀和，方便判断。
// 时间复杂度：N*N*M或者N*M*M

//前缀和为特定值（q）的个数【正整数】 
hash[0]=1;
for(int i=1;i<m;i++)for(int j=i+1;j<=m;j++){for(int k=1;k<=n;k++){hash[sum[k][j]-sum[k][i]]++;if(sum[k][j]-sum[k][i]>=q)ans += hash[sum[k][j]-sum[k][i]-q];}for(int k=1;k<=n;k++)hash[sum[k][j]-sum[k][i]]--;}// i,j：枚举 长/宽
// k：枚举 行数/列数
// 哈希存储前缀和，方便判断。
// 时间复杂度：N*N*M或者N*M*M

---

以下背包问题可参考博客：
（1）

---

（6）0/1背包

题意
给你一堆数据，每种数据只有一个，有空间与价值两个数据，问你在指定的空间内能获得多大的价值。

状态转移方程

 for(int i=1;i<=n;i++){int jud=max(m-(sum[n]-sum[i-1]),w[i]);for(int j=m;j>=jud;j--)f[j] = max(f[j],f[j-w[i]]+c[i]);}// 预处理：无
// i:第i件物品
// j:剩余空间大小
// 时间复杂度：N*MP.S:重点：从后往前枚举

例题
HDU 3466
HDU 2955

---

（7）完全背包

题意
给你一堆数据，每种数据有无数个，有空间与价值两个数据，问你在指定的空间内能获得多大的价值。

状态转移方程

 for(int i=1;i<=n;i++){int jud=max(m-(sum[n]-sum[i-1]),w[i]);for(int j=jud;j<=m;j++)f[j] = max(f[j],f[j-w[i]]+c[i]);}// 预处理：无
// i:第i件物品
// j:剩余空间大小
// 时间复杂度：N*MP.S:重点：从前往后枚举

例题
HDU 2602
HDU 1114

（6）最少呼吸根树（又是自己乱取的名）

题意
给你一颗树，每个节点可以控制与自己距离为K的节点，询问控制所有的边所需要的最少节点数 或者 控制所有的点所需要的最少节点数。

P.S:此类题事实上可能用贪心更快更准。。。

状态转移方程

//每个节点可以控制与自己距离为1的节点
//询问控制所有的边所需要的最少节点数void dfs(int root)
{
    dp[root][0] = 0;
    dp[root][1] = 1;
    for(int k=son[root];k!=-1;k=bro[k])
    {
        dfs(k);
        dp[root][0] += dp[k][1];
        dp[root][1] += min(dp[k][0],dp[k][1]);
    }
}// 预处理：root,fa[i],son[i],bro[i]
// ans = min(dp[root][0],dp[root][1])
// 0/1：不选/选择这个点
// root：以这个节点为根的子数
// 时间复杂度：。。。。。。