转移dp简单数学数论

1.转移dp问题

昨天的练习赛上有一个很好玩的起终点问题，第一时间给出bfs的写法。

但是写到后面发现不行，还得是的dp转移的写法才能完美的解决这道题目。

每个格子可以经过可以不经过，因此它的状态空间是2^（n*m），但是n,m的数据范围是500，显然是不可取的。bfs适用于计数或者最短距离，而不是最大和或最优路径问题。

故：对于最大和的问题dp是最合适的选择。

题目意思：

给定起点终点，每个点只能经过一次，找到最大的路径和，并且只能向下向右走动。

思路：

既然是dp那么一点有初始化，很容易想到第一列一定是固定的，因为该列只能像下走动（从起始点开始）。

那么之后我们就对每一列赋值（从第一列开始，每一列的状态都是从前面一列转移过来的）。

对于某一列的赋值，我们可以从头开始往下走，也可以是从尾开始走到第一行在进行继续走，那么这里就分成了两种情况。

我们先任意求出一种情况，然后在慢慢的用前缀和进行维护（因为是一条线下的，前缀和维护方便）。（毕）

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int nima=8e18;
int a[504][504];
void solve(){int n,m;cin>>n>>m;int s,t;cin>>s>>t;s--,t--;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}vector<vector<int>> dp(n,vector<int>(m,-nima));//这里的dp[i][j]的意思是从[s][0]开始到[i][j]的最大贡献// 初始化第一列的值int sum=a[s][0];for(int i=s;;){//一共要遍历s次dp[i][0]=sum;  // 初始化环形路径的第一个点i=(i+1)%n;     // 环形移动sum+=a[i][0];   // 累加路径上的值if(i==s) break; // 回到起点时结束}// 动态规划处理每一列for(int i=1;i<m;i++){int cnt=-nima;int sum=0;vector<int> pre(n);  // 前缀和数组// 正向遍历，计算从上方转移的最大值for(int j=0;j<n;j++){cnt=max(cnt,dp[j][i-1]-sum);  // 维护最大值，从左边过来的sum+=a[j][i];                   // 累加当前列的值dp[j][i]=cnt+sum;              pre[j]=sum;                     // 记录前缀和，这个sum是列环形状态下的前缀和}cnt=-nima;// 反向遍历，处理环形路径的情况for(int j=n-1;j>=0;j--){if(j!=n-1) dp[j][i]=max(dp[j][i],cnt+pre[j]);// 计算从下方转移的最大值（考虑环形路径）if(j!=0) cnt=max(cnt,dp[j][i-1]+pre[n-1]-pre[j-1]);}}cout<<dp[t][m-1]<<endl;
}signed main(){int ac=1;while(ac--)  solve();return 0;
}

2.简单数学

这次的团队赛有个简单数学问题，挺有意思的。

题目意思：

给出一个数组，找出最大贡献（每个贡献是相邻两个数字之差的绝对值）。

思路：

我们可以根据题目给的样例找到....

1 2 3 4 5 6 的最大贡献是9，即（3,4）(2,5) （1,6）状态下贡献是最大的。

我们进行改变之后发现....

3 2 1 4 5 6的最大贡献也是9，即（1,4）（2,5）（3,6）状态下贡献是最大的。

之后在进行任意举列子之后我们发现....

一组数据进行排序后每次最大贡献取法是首位找（毕）

小tips：数学问题，大胆猜，先排序，然后...（看看能不能瞎猫碰到死耗子）

#include<bits/stdc++.h>
using namespace std;
#define int long longinline void solve(){int n; cin >> n;vector<int> a(2 * n);for(int i = 0; i < 2 * n; i++) cin >> a[i];sort(a.begin(), a.end());//排序int answer = 0;for(int i = 0; i < n; i++) {answer+= abs(a[i] - a[2 * n - 1 - i]);//首位之差，参考1 2 3 4 5 6这个样例}cout << answer << endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t; cin >> t;while(t--) solve();return 0;
}

3.数论

这次的数论有点点绕...

 题目意思：

给定一个数是好数m，只有m形如k！或者为偶数的条件下才成立。

给定一个数a，找到最少的分类情况k，使得k个好数之后是a。

思路：

观察题目的数据范围我们看到，n<=10^12，而且有t组数据，最好做一个状态压缩。

我们先对阶乘进行赋初值，15!>10^12。

每次减去1到15的阶乘，最后加上二进制中1的个数就是答案，每次枚举维护一个最小值即可。（毕）

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pii pair<int, int> 
vector<int> v;inline void solve() {int sum = 1,i=1;  // 初始化阶乘结果为 1while(sum<=1e12){sum*=i++;v.push_back(sum);}//sort(v.begin(), v.end());  // 对向量 v 进行排序// 去除重复的阶乘结果//v.erase(unique(v.begin(), v.end()), v.end());int m = v.size();  int n;cin >> n; int ans = 1e9 + 7;// 遍历所有可能的子集（通过位掩码的方式）for (int i = 0; i <= (1 << m) - 1; i++) {int res = n;  // 初始化 res 为 n// 遍历每一位，检查是否在子集中for (int j = 0; j < m; j++) {if ((1 << j) & i)  // 如果第 j 位在子集 i 中res -= v[j];  // 从 res 中减去对应的阶乘值}if (res < 0) continue;  // 如果 res 为负数，跳过当前子集// 计算当前子集的位数和剩余数的位数之和，并更新最小值ans = min(ans, (int)__builtin_popcountll(res) + __builtin_popcountll(i));}cout << ans << endl;
}
signed main() {int nc;cin >> nc;while (nc--) solve();  
}