目前进度——动态规划1：线性dp、背包问题，区间
好题
1012 [NOIP1999]拦截导弹
前言
本题不重要，重要的是关于伪单调栈求最长单调子序列的理解。
伪单调栈求最长单调子序列的一些理解重点
- 最终伪单调栈中的序列不一定是最长单调子序列。
- 以最长上升子序列为例，解释操作的意图。若目前元素 \(a_i\) 大于栈首元素，则可直接接在栈首，成为新的栈首；否则，需要在栈中二分找第一个大于等于 \(a_i\) 的数，使之被替换成 \(a_i\)。接下来介绍否则后操作的意图。易发现，\(a_i\) 除通过大于栈首而成为栈首之外，还可通过让栈首第一个大于等于其而替换掉栈首，因为根据贪心，这么做可以在后面接更多的数。于是产生新的疑惑：为何不能只判断栈首是否是第一个大于等于 \(a_i\) 的数，如果是替换掉即可，为什么还要替换其他位置？因为在遍历到 \(a_i\) 之前，可能有多个栈元素因无法成为栈首而作为了栈中的其他元素，这些元素虽然无法成为栈首但仍有可能比 \(a_i\) 更有资格成为栈首，所以 \(a_i\) 要成为栈首就要先满足比他们都有资格然后才可以去挑战栈首。故替换其他位置的意图，就是要存储这些虽然不是栈首但有一定资格成为栈首的元素。
- 我们易发现在最长上升子序列中，寻找的是第一个小于等于 \(a_i\) 的栈元素；在最长不下降子序列中，寻找的是第一个小于 \(a_i\) 的元素。为何会有此差别？思考易得，若为小于等于则栈中无值大小相等的元素，满足上升；小于则栈中可有值相等的元素，满足不下降。
1014 小A买彩票
标签
概率DP
思路
- 等权重的递推概率 DP，唯一的注意点是盈利的最小值是负值，需要变换零点，使得盈利的等价最小值为 \(0\) 或 \(1\)。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxw=110,maxn=32;
long long dp[maxn][maxw],dw[4]={-1,-2,0,1},n;
long long gcd(long long a,long long b)
{
if(a<b) swap(a,b);
if(b==0) return a;
else return gcd(b,a%b);
}
int main()
{
scanf("%lld",&n);
memset(dp,-1,sizeof(dp));
dp[0][61]=1;
for(int i=0;i<n;i++)
{
for(int j=1;j<=n+61;j++)
{
if(dp[i][j]==-1) continue;
for(int k=0;k<4;k++)
{
if(dp[i+1][j+dw[k]]==-1)
dp[i+1][j+dw[k]]=0;
dp[i+1][j+dw[k]]+=dp[i][j];
}
}
}
long long sum=0,sumi=0;
for(int i=1;i<=n+61;i++)
if(dp[n][i]!=-1)
{
sum+=dp[n][i];
if(i>=61) sumi+=dp[n][i];
}
long long g=gcd(sum,sumi);
if(sumi==0) printf("0/1");
else printf("%lld/%lld",sumi/g,sum/g);
return 0;
}