【无标题】

纸带

有一张长1*n的纸带，由n个格子组成。初始有一个点在n号格子（即左数第n个）中。
假设现在这个点在x (x>1）号格子，每次可以对这个点进行如下操作中的一种：

????????
减法：选择一个 [1,x-1]?中的正整数y，将点移动到 x - y号格子中
除法：选择一个[2,x]中的正整数z，将点移动到[x/z]号格子中
当点在1号格子中时无法移动，操作结束。

????????
求将点从 n号格子移到 1号格子的方案数，答案对给定的模数取模。
两个方案不同当且仅当有一步选择的操作或选择的数不同。

输入：

3 998244353

思路：

我们先设置dp[i]表示从i到n的方案数。

那么减法操作中：i可以移动到[1,i-1]中的任意一个格子。反过来可以认为：i可以从i+1到n转移过来。所以得出dp[i]=dp[i+1]+…dp[n]；（使用后缀和即可）

然后除法操作中：i可以移动到[1,i/2]中的任意一个格子。反过来可以认为：i可以从x/2==i的任意x移动过来。所以得出dp[i]+=sum[i*j]-sum[i*j+j]（i*j<=n）

#include <bits/stdc++.h>
using namespace std;
const int N=4e6+5;
int n,mod,dp[N],sum[N];

int main(){
	cin>>n>>mod;
	dp[n]=sum[n]=1;
	for(int i=n-1;i>=1;i--){
		dp[i]=sum[i+1];//减法
		for(int j=2;j*i<=n;j++){//除法
			int r=min(n,i*j+j-1);
			dp[i]=(dp[i]+sum[i*j]-sum[r+1])%mod;
		}
		sum[i]=(sum[i+1]+dp[i])%mod;
	}	
	cout<<dp[1];
}

????????

????????

围栏木桩

?输入：
3
9 10 1 9 8 7 6 3 4 6
3 100 70 102
6 40 37 23 89 91 12

思路：

其实就是先找最长上升子序列，然后再求有多少个最长的上升子序列。

首先设置dp[i]表示以i结尾的最长上升子序列。

转移：（i能拼在j后面的话）dp[i]=max(dp[j])+1;

那么要求有多少个最长上升子序列的话就要进行修改，

把dp[i]=max(dp[j])+1改成?if(dp[j]+1>dp[i]) dp[i]=dp[j]+1;

这样的话就能知道什么时候修改了dp[i]，当修改dp[i]的时候自然是因为i可以拼在j之后且拼完后dp[i]会变大。

故：f[i]=f[j]

当dp[j]+1=dp[i]时候，说明i即便拼在j后面dp也不会变化，那就说明拼在这个j后面也是最优解。

故：f[i]+=f[j]

类似最短路径个数问题嘛！

#include <bits/stdc++.h>
using namespace std;
const int N=27;
int n,m,h[N],dp[N],f[N],ans1,ans2;

int main(){
	cin>>m;
	while(m--){
		cin>>n;
		ans1=0;ans2=0;
		for(int i=1;i<=n;i++){
			cin>>h[i];
			dp[i]=f[i]=1;
		}
		for(int i=2;i<=n;i++)
			for(int j=i-1;j;j--){
				if(h[j]<=h[i]){
					if(dp[j]+1>dp[i]){//更新最优解就继承
						dp[i]=dp[j]+1;
						f[i]=f[j];
					}
					else if(dp[j]+1==dp[i])//当前的j也是可以使变成最优解的j
						f[i]+=f[j];
				}
			}
		for(int i=1;i<=n;i++)
			ans1=max(ans1,dp[i]);
		for(int i=1;i<=n;i++)
			if(dp[i]==ans1)
			ans2+=f[i];
		cout<<ans1<<" "<<ans2<<'\n';
	}	
}