dp杂题

dp[i][0]表示i-1和i+1都不是雷的情况 =s[i]==0
dp[i][1]表示i-1是雷，i+1不是雷的情况 =s[i]==1
dp[i][2]表示i-1不是雷，i+1是雷的情况 =s[i]==1
dp[i][3]表示i-1是雷，i+1也是雷的情况 =s[i]==2
dp[i][4]表示i本身是雷 =s[i]==*

注意dp状态在设计的时候要考虑分类的条件

转移：当

s[i]==0

时

dp[i][0]=dp[i-1][0]+dp[i-1][1]

当

s[i]==1

时

dp[i][1]=dp[i-1][4]

dp[i][2]=dp[i-1][0]+dp[i-1][1]

当

s[i]==2

时

dp[i][3]=dp[i-1][4]

当

s[i]==*

时

dp[i][4]=dp[i-1][2]+dp[i-1][3]+dp[i-1][4]

当

s[i]==?

时，前四种都可以

dp[i][0]=dp[i-1][0]+dp[i-1][1]

dp[i][1]=dp[i-1][4]

dp[i][2]=dp[i-1][0]+dp[i-1][1]

dp[i][3]=dp[i-1][4]

dp[i][4]=dp[i-1][2]+dp[i-1][3]+dp[i-1][4]

初值：

dp[0][0]=dp[0][2]=1

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1e6+10,mod=1e9+7;
int n;
string s;
int dp[2][5];
signed main()
{
	cin>>s;
	n=s.size();
	s=" "+s;
	dp[0][0]=dp[0][2]=1;
	for(int i=1,o=1;i<=n;i++,o^=1)
	{
		for(int j=0;j<5;j++)
			dp[o][j]=0;
		if(s[i]=='*')
			dp[o][4]=(dp[o^1][2]+dp[o^1][3]+dp[o^1][4])%mod;
		else if(s[i]=='0')
			dp[o][0]=(dp[o^1][0]+dp[o^1][1])%mod;
		else if(s[i]=='1')
		{
			dp[o][1]=dp[o^1][4]%mod;
			dp[o][2]=(dp[o^1][0]+dp[o^1][1])%mod;
		}
		else if(s[i]=='2')
			dp[o][3]=dp[o^1][4]%mod;
		else if(s[i]=='?')
		{
			dp[o][4]=(dp[o^1][2]+dp[o^1][3]+dp[o^1][4])%mod;
			dp[o][0]=(dp[o^1][0]+dp[o^1][1])%mod;
			dp[o][1]=dp[o^1][4]%mod;
			dp[o][2]=(dp[o^1][0]+dp[o^1][1])%mod;
			dp[o][3]=dp[o^1][4]%mod;
		}
	}
	cout<<(dp[n&1][0]+dp[n&1][1]+dp[n&1][4])%mod;
	return 0;
}

CF41D Pawn

容易想到二维dp，这是我们发现不好在k+1的倍数的条件下转移，所以==加维==，并且注意数据范围，每行最多选一个，这一个数最大是9，所有数的总和最多是 900 ，不会炸

dp[i][j][k]

表示在i行j列可不可能收集到k的豆子

dp[i][j][k]=dp[i+1][j-1][k-a[i][j]] \ or \ dp[i+1][j+1][k-a[i]]

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
const int N=100+10;
bool dp[N][N][9*N];
bool zy[N][N][9*N];//输出方案用的，1从左边转移，0从右边转移
int n,m,K;
int a[N][N];
int max_sum;
vector<char> ans;
int ans_id;
void dfs(int x,int y,int num)
{
	if(x==n)
	{
		ans_id=y;
		return ;
	}
	if(zy[x][y][num])
	{
		ans.emplace_back('R');
		dfs(x+1,y-1,num-a[x][y]);
	}
	else
	{
		ans.emplace_back('L');
		dfs(x+1,y+1,num-a[x][y]);
	}
}
signed main()
{
	cin>>n>>m>>K;
	char ch;
	for(int i=1;i<=n;i++)
	{
		int tmp_max=0;
		for(int j=1;j<=m;j++)
		{
			ch=getchar();
			a[i][j]=ch-'0';
			tmp_max=max(tmp_max,a[i][j]);
		}
		getchar();
		max_sum+=tmp_max;
	}
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=m;j++)
//			cout<<a[i][j]<<" ";
//		cout<<endl;
//	}
	for(int i=1;i<=m;i++)
		dp[n+1][i][0]=1;
	for(int i=n;i>=1;i--)
	{
		for(int j=m;j>=1;j--)
		{
			for(int k=a[i][j];k<=max_sum;k++)
			{
				if(dp[i+1][j-1][k-a[i][j]])
					zy[i][j][k]=1;
				else
					zy[i][j][k]=0;
				dp[i][j][k]=dp[i+1][j-1][k-a[i][j]]||dp[i+1][j+1][k-a[i][j]];
			}
		}
	}
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=m;j++)
//		{
//			for(int k=1;k<=max_sum;k++)
//			{
//				cout<<i<<" "<<j<<" "<<k<<" ";
//				cout<<dp[i][j][k]<<endl;
//			}
//			cout<<endl;
//		}
//		cout<<endl<<endl;
//	}
	int max_num=-1,id;
	for(int i=1;i<=m;i++)
	{
		for(int j=0;;j++)
		{
			if(j*(K+1)>max_sum)
				break;
			if(dp[1][i][j*(K+1)])
			{
				if(j*(K+1)>max_num)
				{
					max_num=j*(K+1);
					id=i;
				}
			}
		}
	}
	if(max_num==-1)
	{
		cout<<-1;
		return 0;
	}
	dfs(1,id,max_num);
	cout<<max_num<<endl;
	cout<<ans_id<<endl;
	reverse(ans.begin(),ans.end());
	for(auto i:ans)
		cout<<i;
	return 0;
}

CF1485F Copy or Prefix Sum

题解

实现细节很多，注意初值dp[0]和sum[0]都是1

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=2e5+10,mod=1e9+7;
int n;
int b[N];
map<int,int> dp;
void solve()
{
//	for(int i=1;i<=n;i++)
//		b[i]=0;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>b[i];
	dp.clear();
	dp[0]=1;
	int sum=1,py=0;
	for(int i=1;i<=n;i++)
	{
		int add=((sum-dp[0-py])%mod+mod)%mod;
		sum=((sum+add)%mod+mod)%mod;
		py+=b[i];
		dp[b[i]-py]=((dp[b[i]-py]+add)%mod+mod)%mod;
	}
	cout<<(sum%mod+mod)%mod<<endl;
}
signed main()
{
	int T;
	cin>>T;
	for(int i=1;i<=T;i++)
		solve();
	return 0;
}

CF1481E Sorting Books

困难题

设

f[i]

表示在区间

[i,n]

中不用移动的数有多少种

l[i]

表示值为

i

的数在出现在最左边的下标，

r[i]

表示值为

i

的数出现在最右边的下标，

tot[i]

表示值为

i

的数在区间

[i,n]

中出现的次数有三种转移

$dp[i]=dp[i+1]$ ,代表这直接将这一本移动到后面
$dp[i]=tot[a[i]]+dp[r[a[i]]+1] (i==l[a[i]])$ ，代表着将区间 $l[a[i]]$ 到 $r[a[i]]$ 这一段中的所有其他书全部移走，不用移动的书只有颜色为 $a[i]$ 的书
$dp[i]=tot[a[i]] (i!=l[a[i]])$ 代表着将已经遍历到的区间 $[i,n]$ 中的所有颜色为 $a[i]$ 的书移动到最后关于为什么只有在当前点是 $a[i]$ 出现的左端点时，才进行2转移，我的理解是只有在左端点时，我才完整知道这个区间内的信息，即知道所有的 $a[i]$ 的数量，才能进行2转移，否则不对

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
const int N=5e5+10;
int n;
int l[N],r[N],tot[N],dp[N];
int a[N]; 
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		if(!l[a[i]])
			l[a[i]]=i;
	for(int i=n;i>=1;i--)
		if(!r[a[i]])
			r[a[i]]=i;
	for(int i=n;i>=1;i--)
	{
		tot[a[i]]++;
		if(i==l[a[i]])
			dp[i]=max(dp[i],dp[r[a[i]]+1]+tot[a[i]]);
		else
			dp[i]=max(dp[i],tot[a[i]]);
		dp[i]=max(dp[i],dp[i+1]);
	}
	cout<<n-dp[1]<<endl;
	return 0;
}

CF570E Pig and Palindromes

首先，回文可以看作是两个相同字符串拼起来，所以可以两边同时相中间找，类似于双向dfs

设

dp[i][j][k]

表示一共走了

i

步，第一个人的横坐标为

j

，第二个人的横坐标为

k

的方案数

可以推出：第一个人的纵坐标：

y_1=i-j+1

同理，注意第二个是倒着的：

y_2=n-(i-(m-k))+1

转移：两个都横着走，一个横一个竖，两个竖

dp[i][j][k]=dp[i-1][j-1][k+1]+dp[i-1][j][k+1]+dp[i-1][j-1][k]+dp[i-1][j][k] (s[j][i-j+1]==s[k][n-(i-(m-k))+1])

滚动优化一维

初值

dp[1][1][n] = 1

答案要判断(n+m-1)(这就是出来的串的长度)的奇偶性，奇数的话在对角线上，偶数在对角线两边

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=500+10,mod=1e9+7;
int dp[2][N][N];
int n,m;
string s[N];
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		s[i]=" "+s[i];
	}
	if(s[1][1]!=s[n][m])
	{
		cout<<0;
		return 0;
	}
	dp[0][1][n]=1;
	int o=1;
	int flg=(n+m-1)&1;
	for(int i=2;i<=(n+m-1)/2+flg;i++,o^=1)
	{
		memset(dp[o],0,sizeof(dp[o]));
		for(int j=1;j<=min(i,n);j++)
			for(int k=n;k>=max(n-i,j);k--)
				if(s[j][i-j+1]==s[k][n-(i-(m-k))+1])
					dp[o][j][k]=(dp[o^1][j-1][k+1]+dp[o^1][j][k+1]+dp[o^1][j-1][k]+dp[o^1][j][k])%mod;
	}
	o^=1;//注意
	int ans=0;
	if((n+m-1)&1)
	{
		for(int i=1;i<=n;i++)
		{
			ans+=dp[o][i][i];
			ans%=mod;
		}
		cout<<ans;
	}
	else
	{
		for(int i=1;i<=n;i++)
		{
			ans+=dp[o][i][i]+dp[o][i][i+1];
			//(i,(n+m-1)/2-i+1),(i+1,(n+m-1)/2-(i+1)+1)
			//(i,(n+m-1)/2-i+1),(i+1,(n+m-1)/2-i)
			ans%=mod;
		}
		cout<<ans;
	}
	return 0;
}

CF467D Fedor and Essay

首先，容易想到可替换的单词连边并对每一个问文章里的单词进行

dfs

的方法，但超时

考虑优化，用

dijkstra

代替

dfs

的过程，就可以了

注意代码细节，如优先队列的重载运算符是反的（如我要长度小的在前边，就要在重载小于的时候写

len1>len2

），部分量在

dijkstra

时不能改

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1e5+10;
string s;
int n,m;
struct dataa
{
	int cnt_c,len,id;
	int cnt_num;
	bool is_artical;
	friend bool operator <(dataa t1,dataa t2)
	{
		if(t1.cnt_c!=t2.cnt_c)
			return t1.cnt_c>t2.cnt_c;
		else
			return t1.len>t2.len;
	}
}c[N];
int cnt_c;
int cnt_id;
unordered_map<string,int> mp;
int h[N],to[N],ne[N],idx;
void add(int u,int v)
{
	to[++idx]=v;
	ne[idx]=h[u];
	h[u]=idx;
}
bool vst[N];
void dijkstra()
{
	priority_queue<dataa> q;
	for(int i=1;i<=cnt_c;i++)
		q.emplace(c[i]);
	while(!q.empty())
	{
		auto u=q.top();
		q.pop();
		for(int i=h[u.id];i;i=ne[i])
		{
			int v=to[i];
			if(c[v].cnt_c>u.cnt_c)
			{
				bool flg=0;
				int tmp=c[v].cnt_num,tmp2=c[v].id;
				if(c[v].is_artical)
					flg=1;
				c[v]=u;
				c[v].is_artical=flg;
				c[v].cnt_num=tmp;
				c[v].id=tmp2;
				q.emplace(c[v]);
			}
			else if(c[v].cnt_c==u.cnt_c&&c[v].len>u.len)
			{
				bool flg=0;
				int tmp=c[v].cnt_num,tmp2=c[v].id;
				if(c[v].is_artical)
					flg=1;
				c[v]=u;
				c[v].is_artical=flg;
				c[v].cnt_num=tmp;
				c[v].id=tmp2;
				q.emplace(c[v]);
			}
		}
	}
}
signed main()
{
	cin>>m;
	for(int i=1,cnt=0;i<=m;i++)
	{
		cin>>s;
		cnt=0;
		for(int j=0;j<(signed)s.size();j++)
		{
			if(s[j]>='A'&&s[j]<='Z')
			{
				s[j]=s[j]-'A'+'a';
			}
			if(s[j]=='r')
				cnt++;
		}
		if(mp.find(s)==mp.end())
		{
			cnt_c++;
			c[cnt_c].id=cnt_c;
			c[cnt_c].cnt_c=cnt;
			c[cnt_c].len=s.size();
			c[cnt_c].is_artical=1;
			c[cnt_c].cnt_num=1;
			mp[s]=cnt_c;
		}
		else
			c[mp[s]].cnt_num++;
	}
	cin>>n;
	for(int i=1,cnt=0;i<=n;i++)
	{
		cin>>s;
		cnt=0;
		for(int j=0;j<(signed)s.size();j++)
		{
			if(s[j]>='A'&&s[j]<='Z')
			{
				s[j]=s[j]-'A'+'a';
			}
			if(s[j]=='r')
				cnt++;
		}
		if(mp.find(s)==mp.end())
		{
			cnt_c++;
			c[cnt_c].id=cnt_c;
			c[cnt_c].cnt_c=cnt;
			c[cnt_c].len=s.size();
			c[cnt_c].cnt_num=1;
			mp[s]=cnt_c;
		}
		int id1=mp[s];
		cin>>s;
		cnt=0;
		for(int j=0;j<(signed)s.size();j++)
		{
			if(s[j]>='A'&&s[j]<='Z')
			{
				s[j]=s[j]-'A'+'a';
			}
			if(s[j]=='r')
				cnt++;
		}
		if(mp.find(s)==mp.end())
		{
			cnt_c++;
			c[cnt_c].id=cnt_c;
			c[cnt_c].cnt_c=cnt;
			c[cnt_c].len=s.size();
			c[cnt_c].cnt_num=1;
			mp[s]=cnt_c;
		}
		add(mp[s],id1);
	}
	dijkstra();
	int ans1=0,ans2=0;
	for(int i=1;i<=cnt_c;i++)
	{
		if(!c[i].is_artical)
			continue;
		ans1+=c[i].cnt_c*c[i].cnt_num;
		ans2+=c[i].len*c[i].cnt_num;
	}
	cout<<ans1<<" "<<ans2<<endl;
	return 0;
}

CF75D Big Maximum Sum

首先，看到题目就可以想到，最大子段和一定是小数组的最大子段和，或者一个或很多小前缀后缀拼起来，所以设

dp[i][0/1]

表示以第

i

个结尾，不一定选这个对应的小数组的全部/一定选小数组的全部的最大子段和

转移：

dp[i][0]=max(dp[i-1][1]+pre \ max[big[i]],max \ sum[big[i]])

dp[i][1]=max(dp[i-1][1]+pre \ sum[big[i]],suf \ max[big[i]])

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=50+10,M=2.5e5+10,L=5e3+10;
int n,m;
int siz[N];
int small[N][L];
int pre_sum[N][L];
int suf_sum[N][L];
int suf_max[N];
int dp_s[L];
int max_sum[N];
int pre_max[N];
int big[M];
int dp[M][2];
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>siz[i];
		for(int j=1;j<=siz[i];j++)
		{
			cin>>small[i][j];
			pre_sum[i][j]=pre_sum[i][j-1]+small[i][j];
		}
		suf_max[i]=-1e9;
		for(int j=siz[i];j>=1;j--)
		{
			suf_sum[i][j]=suf_sum[i][j+1]+small[i][j];
			suf_max[i]=max(suf_sum[i][j],suf_max[i]);
		}
		for(int j=1;j<=siz[i];j++)
			dp_s[j]=-1e9;
		max_sum[i]=pre_max[i]-1e9;
		for(int j=1;j<=siz[i];j++)
		{
			dp_s[j]=max(dp_s[j-1]+small[i][j],small[i][j]);
			max_sum[i]=max(max_sum[i],dp_s[j]);
			pre_max[i]=max(pre_sum[i][j],pre_max[i]);
		}
	}
//	for(int i=1;i<=n;i++)
//		cout<<max_sum[i]<<" ";
//	cout<<endl;
	for(int i=1;i<=m;i++)
		cin>>big[i];
	for(int i=0;i<=m;i++)
		dp[i][0]=dp[i][1]=-1e9;
	for(int i=1;i<=m;i++)
	{
		dp[i][0]=max(dp[i-1][1]+pre_max[big[i]],max_sum[big[i]]);
		dp[i][1]=max(dp[i-1][1]+pre_sum[big[i]][siz[big[i]]],suf_max[big[i]]);
	}
	int ans=-1e9;
	for(int i=1;i<=m;i++)
	{
		ans=max({ans,dp[i][0],dp[i][1]});
//		cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
	}
	cout<<ans;
	return 0;
}

优化后：

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=50+10,M=2.5e5+10,L=5e3+10;
int n,m;
int siz[N];
int small[L];
int pre_sum[N];
int suf_max[N];
int dp_s[2];
int max_sum[N];
int pre_max[N];
int big[M];
int dp[2][2];
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>siz[i];
		for(int j=1;j<=siz[i];j++)
		{
			cin>>small[j];
			pre_sum[i]=pre_sum[i]+small[j];
			pre_max[i]=max(pre_sum[i],pre_max[i]);
		}
		suf_max[i]=-1e9;
		int suf_sum=0;
		for(int j=siz[i];j>=1;j--)
		{
			suf_sum=suf_sum+small[j];
			suf_max[i]=max(suf_sum,suf_max[i]);
		}
		dp_s[0]=dp_s[1]=-1e9;
		max_sum[i]=pre_max[i]-1e9;
		for(int j=1,o=1;j<=siz[i];j++,o^=1)
		{
			dp_s[o]=max(dp_s[o^1]+small[j],small[j]);
			max_sum[i]=max(max_sum[i],dp_s[o]);
		}
	}
	for(int i=1;i<=m;i++)
		cin>>big[i];
	dp[0][0]=dp[0][1]=dp[1][0]=dp[1][1]=-1e9;
	int ans=-1e9;
	for(int i=1,o=1;i<=m;i++,o^=1)
	{
		dp[o][0]=max(dp[o^1][1]+pre_max[big[i]],max_sum[big[i]]);
		dp[o][1]=max(dp[o^1][1]+pre_sum[big[i]],suf_max[big[i]]);
		ans=max({ans,dp[o][0],dp[o][1]});
	}
	cout<<ans;
	return 0;
}

CF894E Ralph and Mushrooms

首先，一个环上可以连续走，所以要一直走到蘑菇全部为0的时候，然后缩点，在新图上dp，因为每条边只能走一遍

同时，我们注意到，一条边单次被减的是

i*(i+1)/2

所以次数一定在

\sqrt n

左右，所以直接正负找5个

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1e6+10;
int n,m;
int h[N],to[N],ne[N],w[N],idx;
int h1[N],to1[N],ne1[N],w1[N],idx1;
struct dataa
{
	int u,v,c;
}edge[N];
void add(int u,int v,int c)
{
	to[++idx]=v;
	w[idx]=c;
	ne[idx]=h[u];
	h[u]=idx;
}
void add1(int u,int v,int c)
{
	to1[++idx1]=v;
	w1[idx1]=c;
	ne1[idx1]=h1[u];
	h1[u]=idx1;
}
int dfn[N],low[N],time_stamp,scc_cnt,id[N],stk[N],t;
bool in_stk[N];
int sum[N];
int val[N];
void init(int n)
{
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+i*(i+1)/2;
}
int calc(int w)
{
	int tmp=sqrtl(w*2);
	int ans=0;
	for(int i=max(tmp-5,0ll);i<=tmp+5;i++)
	{
		if(i*(i+1)/2>=w)
		{
			ans=i-1;
			break;
		}
	}
	return w*(ans+1)-sum[ans];
}
void tarjin(int u)
{
	dfn[u]=low[u]=++time_stamp;
	stk[++t]=u;
	in_stk[u]=1;
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(!dfn[v])
		{
			tarjin(v);
			low[u]=min(low[u],low[v]);
		}
		if(in_stk[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		int cur;
		scc_cnt++;
		do{
			cur=stk[t--];
			in_stk[cur]=0;
			id[cur]=scc_cnt;
		}while(cur!=u);
	}
}
int ans[N];
int dfs(int u)
{
	if(ans[u])
		return ans[u];
	for(int i=h1[u];i;i=ne1[i])
	{
		int v=to1[i];
		ans[u]=max(ans[u],w1[i]+dfs(v));
	}
	ans[u]+=val[u];
	return ans[u];
}
int s;
signed main()
{
	cin>>n>>m;
	init(2e4);
	for(int i=1,u,v,c;i<=m;i++)
	{
		cin>>u>>v>>c;
		add(u,v,c);
		edge[idx].u=u;
		edge[idx].v=v;
		edge[idx].c=c;
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
			tarjin(i);
	}
	for(int i=1;i<=idx;i++)
	{
		if(id[edge[i].u]==id[edge[i].v])
		{
			val[id[edge[i].u]]+=calc(edge[i].c);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=h[i];j;j=ne[j])
		{
			int v=to[j];
			if(id[i]!=id[v])
				add1(id[i],id[v],w[j]);
		}
	}
	cin>>s;
	cout<<dfs(id[s]);
	return 0;
}

CF592D Super M

设

dp[u][0/1]

表示以

u

为根的子树中，回到/不回到u的最小时间，转移：

dp[u][0]= \sum (dp[v][0]+2)

dp[u][1]= \sum_{v \ne son[u] } (dp[v][0]+2) \ + \ dp[son[u]][1]+1

son[u]

表示在以

u

为根的子树中，最长的儿子

第二个转移就是先遍历其他儿子，然后走最长的儿子，不回来

然后换根DP，细节见代码：

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
const int N=123456+10;
int n,m;
int id[N];
int flg[N];
int h[N],to[N<<1],ne[N<<1],idx;
int dp[N][2];
int son[N],nxtson[N];
void add(int u,int v)
{
	to[++idx]=v;
	ne[idx]=h[u];
	h[u]=idx;
}
#define val(v) (dp[v][0]-dp[v][1])
/*
flg[u] 以u为根的子树的关键点的数量
dp[u][0/1]回到/不会到u点的最小时间
son[u] u的最长的儿子
nxtson[u] u第二长的儿子
*/
void dfs1(int u,int fa)
{
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==fa)
			continue;
		dfs1(v,u);
		if(!flg[v])//这个子树没有关键点，直接不进去
			continue;
		flg[u]+=flg[v];
		dp[u][0]+=(dp[v][0]+2);
		if(val(v)>=val(son[u]))
		{
			nxtson[u]=son[u];
			son[u]=v;
		}
		else if(val(v)>=val(nxtson[u]))
			nxtson[u]=v;//更新son和nxtson
	}
	if(son[u])
		dp[u][1]=dp[u][0]-(val(son[u]))-1;
}
int final_ans,final_id;
void dfs2(int u,int fa)
{
	for(int i=h[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==fa||!flg[v])
			continue;
		int dpu1=dp[u][1],dpu0=dp[u][0],flgu=flg[u];
		int dpv1=dp[v][1],dpv0=dp[v][0];
		flg[u]-=flg[v];
		dp[u][0]-=(dp[v][0]+2);
		if(v==son[u])//如果v就是原来的长儿子
		{
			if(nxtson[u])//如果有第二长的儿子
				dp[u][1]=dp[u][0]-val(nxtson[u])-1;//这时不能再用原来的son[u]来更新(因为这时son[u]也就是v要作为根)，而因该用次长的儿子
			else
				dp[u][1]=0;//如果没有次长的儿子，说明这个点只有一个儿子，所以dp[u][1]=0;
		}
		else
			dp[u][1]-=(dp[v][0]+2);//如果不是，直接减去贡献即可
		if(flg[u])//如果以u为根的子树中有关键点，就要用dp[u]来改变dp[v]的值
		{
			if(dp[v][0]+dp[u][1]+1<=dp[v][1]+dp[u][0]+2)//如果u可以当v的长儿子
			{
				dp[v][1]=dp[u][1]+dp[v][0]+1;
				nxtson[v]=son[v];
				son[v]=u;
			}
			else//否则，正常更新
			{
				dp[v][1]+=(dp[u][0]+2);
				if(val(u)>=val(nxtson[v]))
					nxtson[v]=u;
			}
			dp[v][0]+=(dp[u][0]+2);//正常更新
		}
		flg[v]+=flg[u];
		if(dp[v][1]<final_ans)
		{
			final_ans=dp[v][1];
			final_id=v;
		}
		else if(dp[v][1]==final_ans&&final_id>v)
			final_id=v;//更新答案
		dfs2(v,u);
		dp[u][0]=dpu0;
		dp[u][1]=dpu1;
		flg[u]=flgu;
		dp[v][0]=dpv0;
		dp[v][1]=dpv1;//还原
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1,u,v;i<n;i++)
	{
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=m;i++)
	{
		cin>>id[i];
		flg[id[i]]=1;
	}
	dfs1(1,0);
	final_ans=min(dp[1][0],dp[1][1]);
	final_id=1;
	dfs2(1,0);
	cout<<final_id<<endl<<final_ans;
	return 0;
}

CF311B 猫咪运输

题解

注意题目中出发时间和结束玩耍的时间均可以是负数，不能和零取

max

。

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1e5+10,P=100+10;
int dp[P][N];
int n,m,p;
int t[N];
int T[N],d[N],h[N];
int dis[N];
int s[N];
int q[N],head,tail;
double y(int i,int k)
{
	return dp[i-1][k]+s[k];
}
double x(int k)
{
	return k;
}
double k(int j)
{
	return t[j];
}
double b(int i,int j)
{
	return dp[i][j]+s[j]-j*t[j];
}
double slope(int i,int k1,int k2)
{
	return (y(i,k1)-y(i,k2))/(x(k1)-x(k2));
}
signed main()
{
	cin>>n>>m>>p;
	for(int i=2;i<=n;i++)
	{
		cin>>d[i];
		dis[i]=dis[i-1]+d[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>h[i]>>T[i];
		t[i]=T[i]-dis[h[i]];
	}
	sort(t+1,t+1+m);
	for(int i=1;i<=m;i++)
		s[i]=s[i-1]+t[i];
	memset(dp,63,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=p;i++)
	{
		head=tail=1;
		for(int j=1;j<=m;j++)
		{
			while(head<=tail-1&&slope(i,q[head+1],q[head])<k(j))
				head++;
			int k=q[head];
			dp[i][j]=dp[i-1][k]+(j-k)*t[j]-(s[j]-s[k]);
			while(head<=tail-1&&slope(i,q[tail-1],q[tail])>slope(i,q[tail],j))
				tail--;
			q[++tail]=j;
		}
	}
	cout<<dp[p][m];
	return 0;
}

CF507D The Maths Lecture

设

dp[i][j][0/1][0/1]

表示处理到了第

i

位，当前这个数模的余数是

j

，前面有没有已经是k的倍数的，有没有前导零

可以数位dp

注意因为求的是包括后缀，所以不能像普通的数位DP一样，从第一位到最后一位（平常虽然是从

len

一直到

0

，但由于在将上界转为数组时，本身就反转了一遍，所以就可以从最后一位向前），而是从最后一位向前DP，所以在新增一位时，要乘上

10^{n-i}

CPP

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1000+10,K=100+10;
int dp[N][K][2][2];
int n,k,m;
int qpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=res*a%k;
		a=a*a%k;
		b>>=1;
	}
	return res%k;
}
int dfs(int cnt,int yushu,bool flg,bool ling)//位数，余数，是否有k的倍数，是否有前导零
{
	if(yushu==0&&!ling)
		flg=1;
	if(!cnt)
		return flg;
	if(dp[cnt][yushu][flg][ling]!=-1)
		return dp[cnt][yushu][flg][ling];
	int res=0;
	if(cnt==1)
	{
		for(int i=1;i<=9;i++)
		{
			res+=dfs(cnt-1,(qpow(10,n-cnt)*i%k+yushu)%k,flg,0),res%=m;
		}
	}
	else
	{
		for(int i=0;i<=9;i++)
		{
			res+=dfs(cnt-1,(qpow(10,n-cnt)*i%k+yushu)%k,flg,ling&&(i==0));
			res%=m;
		}
	}
	dp[cnt][yushu][flg][ling]=res%m;
	return res;
}
signed main()
{
	cin>>n>>k>>m;
	memset(dp,-1,sizeof(dp));
	cout<<dfs(n,0,0,1)<<endl;
	return 0;
}

CF222E Decoding Genome

矩阵优化DP

设

dp[i][j]

表示处理了前

i

位，最后一位是

j

结尾的方案数

转移：

dp[i][j] = \sum_{k,j没有不能出现} dp[i-1][k]

套用矩阵优化

则有(以只有

3

为例)

\begin{bmatrix} dp[i-1][1] \\ dp[i-1][2] \\ dp[i-1][3] \end{bmatrix} \times x = \begin{bmatrix} dp[i][1] \\ dp[i][2] \\ dp[i][3] \end{bmatrix}

文章操作

相关推荐

评论

dp杂题