算法竞赛集训笔记（三）

NOIP2003 普及组 栈
考虑的是这样一个问题：一个操作数序列，

1,2,…,n（图示为 1 到 3 的情况），栈 A 的深度大于 n。

现在可以进行两种操作，

将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）
将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）
问可以构成多少排列？

记忆化搜索

本题关键在于用怎样的数据结构模拟过程，起先我希望使用三个栈来模拟，dfs搜索状态树，然而较为繁琐难写。事实上通过一个二维数组来传递状态量是合理的选择。引入f[i][j]表示中转栈中有j个元素，仍然有i个元素等待进入中转栈的情况下，在原有情况基础上新加多少情况数。

#include<bits/stdc++.h>
using namespace std;
int f[20][20]={0};
long long dfs(int i,int j){
    if(dfs[i][j]) return f[i][j];  //搜过直接return
    if(i==0) return 1    //只能全部出栈
    if(j>0) f[i][j]+=dfs(i,j-1);  //要么出栈一个
    f[i][j]+=dfs(i-1,j+1);               //要么入栈一个
    return f[i][j];

}
int main(){
    int n;
    scanf("%d",&n);
    printf("%lld",dfs(n,0));
}

动态规划

dp关键在于找边界，找递推。并且递推关系一定要是依赖于历史值。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	long long  dp[20][20]={0};
	//i 中间坑多少个数 j原来坑多少个数
	for(int i=0;i<=n;i++) 
	{
		dp[i][0]=1;
	}    //dp边界
	for(int j=1;j<=n;j++)  //注意顺序
	{
		for(int i=0;i<=n;i++)
		{
			if(i==0) dp[i][j]=dp[i][j-1];  //更新边界时特殊情况
			else
			{
				dp[i][j]+=dp[i-1][j]+dp[i+1][j-1];  //要么出要么进
			}
		}
	 } 
	printf("%lld",dp[0][n]);
}

01背包

一种思路是使用二维数组dp，fij，i表示在前i种商品中做选择，j表示花费掉j元方案数。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 110
using namespace std;
int n,m,a[N],f[N][10010];
int main()
{
 scanf("%d%d",&n,&m);
 for(int i=1;i<=n;i++)
   scanf("%d",&a[i]);
 for(int i=0;i<=n;i++) //注意这里要从0开始 
   f[i][0]=1;             //边界
 for(int i=1;i<=n;i++)
   for(int j=1;j<=m;j++)
   {
   	f[i][j]+=f[i-1][j];   //不选a[i]
   	if(j>=a[i])
   	  f[i][j]+=f[i-1][j-a[i]];   //选a[i]
   }
 cout<<f[n][m];
 return 0;
}

另一种思路使用一维数组，f[j]仅仅表示花费j元的方案数，但是注意更新方向。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 110
using namespace std;
int n,m,a[N],f[10010];
int main()
{
   scanf("%d%d",&n,&m);
   for(int i=1;i<=n;i++)
     scanf("%d",&a[i]);
   f[0]=1;
   for(int i=1;i<=n;i++)
     for(int j=m;j>=a[i];j--)   //反向更新，确保f[j]更新使用到的f[j-a[i]]是没有更新过的
     	  f[j]=f[j]+f[j-a[i]];
   cout<<f[m];
   return 0;
}