动态规划进阶

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=6005;

vector<int> node[N]; // 存下属
int r[N],in[N],dp[N][2];

void dfs(int u){
	dp[u][0]=0;
	dp[u][1]=r[u]; // 老板自己去的初始得分就是他自己的幽默值
	
	// 遍历 u 的所有直接下属 v
	for(int i=0;i<node[u].size();i++){
		int v=node[u][i];
		dfs(v); // 必须先让下属算完
		
		// 下属算完后，老板开始总结汇报
		dp[u][0]+=max(dp[v][0],dp[v][1]); // 老板不去：下属去不去都可以，挑个大的
		dp[u][1]+=dp[v][0];               // 老板去：下属绝对不能去
	}
}

void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>r[i];
	for(int i=1;i<n;i++){
		int l,k;
		cin>>l>>k;
		node[k].push_back(l); // k 是老板，l 是下属
		in[l]++; // l 有老板了，入度加 1
	}
	
	// 找最高级别的大老板（没有老板的人，入度为 0）
	int root=1;
	while(in[root]) root++;
	
	dfs(root);
	// 最后比较一下大老板去和不去，哪个得分更高
	cout<<max(dp[root][0],dp[root][1])<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

if((s1 & s2) || ((s1 << 1) & s2) || ((s1 >> 1) & s2)) continue;

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=15,M=1<<10;

int dp[N][M][N*N]; 
int state[M],cnt[M];
int tot=0;

// 把单行所有不挨着的合法放置方法找出来
void init(int n){
	for(int i=0;i<(1<<n);i++){
		if(i&(i<<1)) continue; // 自己这一行不能有挨着的 1
		
		state[++tot]=i;
		int sum=0;
		for(int j=0;j<n;j++){
			if((i>>j)&1) sum++; // 数一数用了几个国王
		}
		cnt[tot]=sum;
	}
}

void solve(){
	int n,k;
	cin>>n>>k;
	init(n);
	
	for(int i=1;i<=tot;i++){
		if(cnt[i]<=k) dp[1][i][cnt[i]]=1;
	}
	
	for(int i=2;i<=n;i++){           // 第 i 行
		for(int j=1;j<=tot;j++){     // 当前行状态
			for(int x=1;x<=tot;x++){ // 上一行状态
				int s1=state[x],s2=state[j]; // s1：上一行，s2：当前行
				// 检查上下两行会不会打架
				if((s1&s2) || ((s1<<1)&s2) || ((s1>>1)&s2)) continue;
				
				for(int c=cnt[j];c<=k;c++){
					dp[i][j][c]+=dp[i-1][x][c-cnt[j]];
				}
			}
		}
	}
	
	int ans=0;
	for(int i=1;i<=tot;i++) ans+=dp[n][i][k];
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;

int dp[20][20];
int digit[20];

// 就像填密码锁：从高位 pos 往低位填
int dfs(int pos,int last,bool limit,bool lead){
	// 拨圈全转完了；本题只计正整数，排除全零路线
	if(pos==0) return !lead;
	
	// 如果没有天花板限制，且不是前导零，并且这个状态以前算过，直接拿来用！(这就是 DP 加速的秘密)
	if(!limit && !lead && dp[pos][last]!=-1) return dp[pos][last];
	
	int res=0;
	// 看看当前这一位最多能拨到几
	int up=limit?digit[pos]:9; 
	
	// 开始尝试拨动这一位的数字 i
	for(int i=0;i<=up;i++){
		// 情况一：前面都是 0，现在这块填的还是 0，那就继续保持前导零状态往下传
		if(lead){
			res+=dfs(pos-1,i,limit&&(i==up),i==0);
		}
		// 情况二：正常填数字 (这里以 Windy 数为例，要求相邻数字差必须 >= 2)
		else if(abs(i-last)>=2){
			res+=dfs(pos-1,i,limit&&(i==up),false);
		}
	}
	
	// 算完之后，如果没有天花板限制和前导零的干扰，就把答案记到一个本子上
	if(!limit && !lead) dp[pos][last]=res;
	return res;
}

int calc(int x){
	if(x<=0) return 0;
	int len=0;
	// 把数字拆成数组，比如 324 拆成 digit[1]=4, digit[2]=2, digit[3]=3
	while(x){
		digit[++len]=x%10;
		x/=10;
	}
	// 从最高位往下搜，上一个数字随便给个不冲突的 -2，初始有天花板，初始也是前导零
	return dfs(len,-2,true,true);
}

void solve(){
	memset(dp,-1,sizeof dp);
	int l,r;
	cin>>l>>r;
	cout<<calc(r)-calc(l-1)<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
const int MOD=1e9+7;

int a[N];
int dp[N][2];  // dp[i][0/1] 记录前 i 个物品，第 i 个不选/选时的 最大收益
int cnt[N][2]; // cnt[i][0/1] 记录对应的 方案数

void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	// 初始化第一个物品
	dp[1][0]=0;    cnt[1][0]=1; // 第一件不选：收益0，方案数为1种（空集也算合法方案）
	dp[1][1]=a[1]; cnt[1][1]=1; // 第一件选：收益a[1]，方案数为1种
	
	for(int i=2;i<=n;i++){
		// 1. 第 i 个不选：前面那个选或不选都可以，我们需要挑一个收益最大的
		if(dp[i-1][0] > dp[i-1][1]){
			dp[i][0] = dp[i-1][0];
			cnt[i][0] = cnt[i-1][0]; // 继承更优者的方案数
		} else if(dp[i-1][0] < dp[i-1][1]){
			dp[i][0] = dp[i-1][1];
			cnt[i][0] = cnt[i-1][1];
		} else {
			// 两边收益一样大，方案数相加
			dp[i][0] = dp[i-1][0];
			cnt[i][0] = (cnt[i-1][0] + cnt[i-1][1]) % MOD;
		}
		
		// 2. 第 i 个选：前面那个绝对不能选
		dp[i][1] = dp[i-1][0] + a[i];
		cnt[i][1] = cnt[i-1][0]; // 方案数完全取决于 i-1 不选的方案数
	}
	
	// 最后在第 n 个选与不选里，再打一次擂台
	int ans_val, ans_cnt;
	if(dp[n][0] > dp[n][1]){
		ans_val = dp[n][0]; 
		ans_cnt = cnt[n][0];
	} else if(dp[n][0] < dp[n][1]){
		ans_val = dp[n][1]; 
		ans_cnt = cnt[n][1];
	} else {
		ans_val = dp[n][0]; 
		ans_cnt = (cnt[n][0] + cnt[n][1]) % MOD;
	}
	cout<<ans_val<<" "<<ans_cnt<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}
/*
输入样例：
4
2 2 2 2
输出样例：
4 3
样例解释：不相邻选择最大和为 4。有 3 种方案：选第1/3个、第1/4个、第2/4个。注意即使全负数，允许不选，最大和为 0，方案数为 1。
*/