dfs+线性dp从1开始做dfs，初始化dp[i][0],dp[i][1]为1dp[i][0]表示i节点,不染色的方案数观察得到dp方程如下：dp[i][1] =dp[i][1]*((dp[j][1]%mod+dp[j][0]%mod)%mod)%mod; dp[i][0] = (dp[i][0]*dp[j][1]%mod)%mod; #include <iostream> #include <vector> using namespace std; const long long mod = 1e9 + 7; int n; vector<int> rt[1...

第一眼此题可能是一个经典的区间dp，即dp[l][r][1],dp[l][r][0]，l，r代表区间，i代表位于r上的位置是否变换,dp的值代表这段区间的权值和状态转移如下：for(int i=l+1;i<=r;i++){if(s[i]!=s[i-1]){dp[l][i][0]=dp[l][i-1][0];dp[l][i][1]=dp[l][i-1][1]+1;}else{dp[l][i][0]=dp[l][i-1][1];dp[l][i][1]=dp[l][i-1][0]+1;}}res+=min(dp[l][r][0],dp[l][r][1]);}}但是超时，注意到，dp[l][i]...

最简单的一集，注意到i永远无法和i+1，i-1发生互动，分别处理偶位和奇位的数字和，判断是否和整体均值相等即可      #include<iostream> #include<vector> using namespace std; #define vt vector #define int long long #define endl "\n" #define pb push_back signed main() { int t;cin >> t; while (t--) {int n;cin >> n;vt<int> a(n +...

在x处bfs一遍，随后用cnt[5005]存入拥有i距离的点个数。期间维护max_point（距离x的最远距离）剪枝。预处理二维01背包节省时间状态方程如下：i表示选择的距离，j表示当前已经选择的方案数dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*cnt[i] #include <iostream> #include<vector> #include<queue> #include<algorithm> using namespace std; #define pb push_back #define vt vector us...