线性DP整理

P1280 尼克的任务 (f[i]表示[i,n]的最长空闲时间，从后向前递推)

不会状态转移

想了两种状态表示：

1. $f[i]$ 表示前 $i$ 个任务的最少工作时间。
2. $f[i]$ 表示前 $i$ 个时刻的最少工作时间。

看了题解的第一个感受

普及组水题！ 我是FW

$f[i]$ 表示 $[i,n]$ 这段时间的最长空闲时间。

1. 如果 $i$ 时刻没有任务的话， $f[i]=f[i+1]+1$ 继承上一个最大空闲的时间。
2. 如果 $i$ 时刻有任务的话， $f[i]=f[i+last[j]]$ 。

$j$ 表示所有在 $i$ 时刻开始的任务 ，$last[j]$ 表示任务 $j$ 的持续时间。$f[i+last[j]]$ 表示从 $i$ 时刻开始的任务结束之后，能够得到的最大空闲时间。

$ans=f[1]$

ll n,m,k,_;
int f[N];// f[i] 表示 [i,n] 的最大空闲时间，ans = f[1] 
struct Node{
	int st,last;
	bool operator < (const Node &a){
		last>a.last;
	}
}node[N];
bool st[N];
/*
需要知道某个时刻有没有任务开始，以及开始任务的持续时间
*/
void solve(){
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		int x;cin>>x;
		st[x]=1;
		node[i].st=x;
		cin>>node[i].last;
	}
	for(int i=n;i>=1;i--){
		if(!st[i]){
			f[i] = f[i+1]+1;
		}
		else{
			for(int j=k;j>=1;j--){
				if(node[j].st==i)//如果这一时刻有任务的话
					f[i] = max(f[i],f[i+node[j].last]);
			}
		}
	}
	
	cout<<f[1]<<endl;
}

P4933 大师 (求方案数)

看题解表示看呆了。

自己思考的时候看到数据范围想到了一个问题：

$n$ 个数构成一个等差数列，可以拿去任意多个元素，问，操作之后，剩余数列仍是等差数列(公差可以不同)的方案数。 $1\le n\le 10^4$ (空集不是等差数列)

输入
3
1 2 3
输出
7

都是什么神仙操作

$f[i][j]$ 表示以第 $i$ 个元素结尾， 并且公差是 $j$ 的等差数列的个数。

const int N=1e3+10,M=1e9+7,mod=998244353;
ll n,m,k,_;
int f[N][41000];
int a[N];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int p = 20000,ans=0;
	for(int i=1;i<=n;i++){
		ans ++;
		for(int j=i-1;j>=1;j--){
            // + 1 指的是只取第i个，别的都不取。
			f[i][a[i]-a[j]+p] += (f[j][a[i]-a[j]+p]+1);
			f[i][a[i]-a[j]+p] %=mod;
			ans +=(f[j][a[i]-a[j]+p]+1);
			ans %=mod;
		}
	}
	cout<<ans<<endl;
}

如果不在dp过程中计数的话。

const int N=1e3+10,M=1e9+7,mod=998244353;
ll n,m,k,_;
int f[N][41000];
int a[N];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int p = 20000,ans=0;
	for(int i=1;i<=n;i++){
		f[i][0]=1;
		for(int j=i-1;j>=1;j--){
			f[i][a[i]-a[j]+p] += (f[j][a[i]-a[j]+p]+1);
			f[i][a[i]-a[j]+p] %=mod;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=2*p;j++){
			ans = (ans + f[i][j])%mod;
		}
	}
	cout<<ans<<endl;
}

P1233 木棍加工 (二维最长上升子序列，dilworth定理)

属于是做一道不会一道了

$dilworth $ 解释 ：

把一个数列划分成 最少 的 最长不升子序列的数目 等价于 原数列 的 最长上升子序列的长度(LIS)。

记忆方法： 不增对应递增，划分对应长度。

1.对于任意一个序列，单调不增子序列最少划分 等于 最长递增子序列的长度。
2.对于任意一个序列，单调递增子序列最少划分 等于 最长不增子序列的长度。

看了题解之后发现非常的神奇。

如果只有一维的话，比如 9 8 7 ,显然只用话费一个时间周期。

如果有两维，我们将其中两维都从大到小排序。

比如(9,1),(8,2) 1 ， 2 组成一个升序，升序就要多花费一个时间周期。

我们想要花费的时间周期最少，所以求的是二维的 最少不增序列的个数。

由于 $dilworth$ 定理，最少不上子序列个数 等价于 最长上升子序列的长度。

经过严格的思考得到的代码，真香。

#include<bits/stdc++.h>
using namespace std;
struct node {
	int l,r;
} a[5100];
int n;
int dp[5100]= {0},ans;
bool cmp(node x,node y) { //compare
	if(x.l==y.l) return x.r>y.r; //按长度排序，长度相同按宽度排序
	return x.l>y.l;
}
int main() {
	cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i].l>>a[i].r; //输入
	sort(a+1,a+1+n,cmp);//排序
	int ans=0;
	for(int i=1;i<=n;i++){
		dp[i]=1;
		for(int j=1;j<i;j++){
			if(a[i].r>a[j].r)
			dp[i] = max(dp[i],dp[j] + 1);
		}
		ans = max(ans,dp[i]);
	}
	cout<<ans<<endl;
	return 0;
}

P5858 「SWTR-03」Golden Sword

（看了眼题解，好像不是我能轻易学会的题），设计到了单调队列优化，斜率优化。