P1280 尼克的任务
题意：
思路：
很明显这一道dp题目，考虑dp[i]的含义，容易想到表示1~n时间内摸鱼时间的最大值。
接下来考虑转移方程。考虑在时间为i时到达岗位开始工作，即在岗时间为i~n。此时如果有任务且不在工作状态，即可考虑从任务结束时间转移过来（在结束时间时未已在任务中）。不难看出这种方式有一个特点，即逆序循环到第i位时，一定处于任务开始或摸鱼状态，因为任务时往后计算的，不对前面有影响。所以在转移时不用担心转移的位置处于任务中。
转移方程：
如果当前位置没有任务，那么\(dp[i] = dp[i+1] + 1\)
如果当前位置有任务，那么\(dp[i] = max(dp[i], dp[i+v[i][j]])\) (v[i][j]表示第i个数的任务的结束位置)
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+5;
int n, k;
vector<int>v[maxn];
int dp[maxn];
//bool fk(sb s, sb b){
// return s.st < b.st;
//}
int main(){
scanf("%d%d", &n, &k);
// for(int i=1; i<=k; i++) pos[i] = 0;
for(int i=1; i<=k; i++){
int p, t;
scanf("%d%d", &p, &t);
v[p].push_back(t);
// a[i].st = p, a[i].end =t;
// pos[st]++;
}
int pos=1;
//sort(a+1, a+1+k, [](sb s, sb b) {return s.st<b.st;});
for(int i=n; i>=1; i--){
if(v[i].size() == 0) dp[i] = dp[i+1] + 1;
else{
for(int j=0; j<v[i].size(); ++j){
// if(a[j].end == i) dp[i] = max(dp[i], dp[i+a[j].end]);
dp[i] = max(dp[i], dp[i+v[i][j]]);
}
}
}
printf("%d", dp[1]);
}
P4310 绝世好题
题意
给定长度为\(n\)（\(n \leqslant 1e5\)）的整数数列\(a\)（\(a_i \leqslant 10^9\)），求a的最长子序列长度，满足子序列相邻元素按位与结果均不为\(0\)。
思路
首先想到的是\(O(n^2)\)的暴力算法：\(dp[i]\)表示以a_i为结尾的序列的最长长度，据题意则可以得到状态转移方程对于\(i \leqslant n, j<i\)，则若 \(a_i \And a_j, 则dp[i] = max(dp[i], dp[j]+1)\)，即本身\((dp[i])\)和以前一位数（第\(j\)位）为结尾的序列的最大值\((dp[j])\)加1。最后的答案即为\(f[i]\)的最大值，因为长度最长的序列的结尾不一定是最后一位：）。
然后您喜提 \(\color{Green}90\) 分的高分：）。
然后我们就必须优化一下：（。
接下来便是了\(O(n)\) 的算法。之前是遍历数组，比较每一个数字是否符合条件。然后我们其实可以在得到每一个数字时判断它第j位（二进制位）是否为1，因为只有有一位都有1的两个数才能相邻。所以可以更改一下dp[i][j]的含义，即为表示最后一个数字第j位为1的最长子序列长度。
转移方程
若第i个数字第j位为1, \(dp[i][j] = max(dp[i-1][k]) + 1\), 其中k为数字i中为1的位。
若第i个数字第j位不为1，\(dp[i][j] = dp[i-1][j]\)
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 32;
int f[maxn];
int main(){
int n, mx, ans=mx=0;
scanf("%d", &n);
// for(int i=1; i<=n; i++) scanf("%d", &a[i]);
// for(int i=1; i<=n; i++) f[i]=1;
// for(int i=1; i<=n; i++){
// f[i] = 1
// for(int j=1; j<i; j++){
// if(a[i] & a[j]) f[i] = max(f[i], f[j]+1);
// }
// ans = max(ans, f[i]);
// }
for(int i=1; i<=n; i++){
int x;
scanf("%d", &x);
for(int j=0; j<=31; j++) if((1<<j) & x) mx = max(mx, f[j]+1);
for(int j=0; j<=31; j++) if((1<<j) & x) f[j] = max(mx, f[j]);
ans = max(mx, ans);
}
printf("%d\n", ans);
}