1.洛谷P5017 摆渡车动态规划,动规,dp枚举,暴力深度优先搜索,NOIp普及组2018
线性DP好题，思路比较常规，主要是考虑剪枝技巧！
/*
1.考虑对所有同学的时间进行排序，问题转化为：
如何将数轴分为长度不小于m的几段，使每段中的点到右端点的距离之和最短
2.设f[i]表示从(0,i]区间内，并以i为右端点结束的最小时间
那么考虑转移：
f[i]=min(f[j]+∑i-t[k])
(i-2*m<=j<=i-m+1)
（为什么是i-2*m的下界？因为如果大于i-2*m,完全可以再分一段，得到不劣
的答案！）
考虑整理一下：
f[i]=min(f[j]+(num[i]-num[j])*i-(sum[i]-sum[j]))
sum[i]表示以i为右端点的所有时间之和
num[i]表示[0,i]范围内的所有点的数目
同时可以考虑剪枝：
if(num[i]==num[j])
f[i]=f[j];
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=4000002;
int num[N],sum[N],n,m,t[N],f[N],tmp,ans=2147483647;
inline int max(int x,int y)
{
return x>y?x:y;
}
inline int min(int x,int y)
{
return x<y?x:y;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&t[i]);
num[t[i]]++;
sum[t[i]]+=t[i];
tmp=max(tmp,t[i]);
}
for(int i=1;i<=tmp+m;i++)
sum[i]+=sum[i-1],num[i]+=num[i-1];
for(int i=1;i<=tmp+m;i++)
{
f[i]=num[i]*i-sum[i];
if(i>=m&&num[i]==num[i-m])
{
f[i]=f[i-m];
continue;
}
for(int j=max(i-m-m+1,0);j<=i-m;j++)
f[i]=min(f[j]+i*(num[i]-num[j])-(sum[i]-sum[j]),f[i]);
}
for(int i=tmp;i<tmp+m;i++)
ans=min(ans,f[i]);
printf("%d",ans);
return 0;
}
2.noip 2018 货币系统 背包问题
实际上，给定n种不同面额的钞票，考虑最多可以消去多少张，保证所有原有的面额可以被凑出来
这样想：把所有的面额按照大小排一下序，如果后面较大的面额可以用前面较小的面额以某种方式凑出来，那么直接就可以舍弃这种面额
如何说明前面的面额可以凑出来后面的呢？
因为没有限制所用的钞票的个数，显然，我们可以将问题转化为：有n个不同体积的物品，可以无限选择，看看是否能凑出体积x
这不就是完全背包裸题吗！
设f[i]表示面额i是否能被凑出
如果f[i]为真，就可以，否则，就用这个面额去更新其他所有用它能更新的面额，相当于把他加入了物品组！
转移方程：f[i]=f[i]|f[i-val[k]];
val[k]表示第k种货币的面额
这个背包的体积应该是这个系统中的最大面额！
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=25002;
int T,n;
int val[N],ans,V;
bool f[N];
int main()
{
scanf("%d",&T);
for(int i=1;i<=T;i++)
{
ans=0;
memset(f,0,sizeof(f));
V=-1;
memset(val,0,sizeof(val));
scanf("%d",&n);
for(int j=1;j<=n;j++)
{
scanf("%d",&val[j]);
V=max(V,val[j]);
}
sort(val+1,val+1+n);
f[0]=1;
for(int j=1;j<=n;j++)
{
if(f[val[j]])
continue;
for(int t=val[j];t<=V;t++)
f[t]=f[t]|f[t-val[j]];
ans++;
}
printf("%d\n",ans);
}
return 0;
}
3.
NOIP 2017 跳房子（线性DP+单调队列套二分）
常规思路，没有想到可以用二分，其实还是可以用单调队列的！
4.NOIP 2016 换教室：概率+期望DP
考虑先预处理出来每个节点的距离，使用floyd
在对每个节点进行DP，设f[i][j][0/1]表示第i个阶段，进行了j次申请后，第j次是否申请的min值，考虑推一下期望方程！
5.NOIP 2015 子串
考虑一个类似于LCA的东西？设f[i][j][k]表示在A中走到i处，在B中走到j处，一共已经找到k个子串使A[1...i]与B[1..j]相匹配
考虑转移？
还需要存储于B[i]匹配的最后一个子串的位置？
的确如此,事实上，我们还需要加一维状态存第i个A中的字符是否被使用了，这样之后在考虑转移就相对较容易了，若a[i]=b[j]，那么可以选a[i]与a[i-1]同时成串，或者选a[i],a[i-1]并且格子单独成，
或者不选a[i-1]让a[i]单独，再或者不选a[i],方案数就是a[i-1]选/不选的和f[i-1][j][k][0]+f[i-1][j][k][1];
6.NOIP 2014 联合权值
考虑用sum[i]表示所有与i节点相连的节点权值和，然后选择出任意一个i相连的节点x
ans+=(sum[i]-x)*x;类似于乘法分配率
for一下所有剩下的节点（保证顺序，没有必要重复找了）
maxn=max(maxn,val[i]*val[j]);
考虑所有距离为2的节点，要么是祖父-孙子关系，要么是兄弟关系；
对于节点i的所有连着的节点，sum[i]表示其全职和，square[i]表示所有i连接节点的权值平方和，然后ans+=sum[i]^2-square[i];
最大值也很好处理，要么是最大*次大，要么是最小*倒数第二小（前提为负数），但是W[i]>0,所以只需要算出来最大和第二大的即可啦！
7.子矩阵NOIP 2014 普及组 暴力枚举+降维DP
考虑选出一个r行c列的子矩阵？
考虑一下用暴力思路，
复杂度：C(n,r)*C(m,c)
正解呢？
我们考虑枚举任意r行的情况，复杂度C(n,r),接着，在已经得到的行的情况上，进行列的情况的DP
设lc[i]表示第i列元素在选出来的行上互相上下之间的差绝对值之和，hc[i][j]表示第i列和第j列同行之间的元素差的绝对值
那么设f[i][j]表示这种行的选择情况下，选出j列的最大值,包括选择第i列
f[i][j]=min(f[k][j-1]+lc[i]+h[k][i])(类似于枚举了一下断点进行转移！)
最后，统计答案即可！
原文：https://www.cnblogs.com/little-cute-hjr/p/11774012.html