本文主要是介绍arc 166 b，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include<bits/stdc++.h>
using namespace std;
using VI = vector<int>;
using ll = long long;
using PII = pair <ll , int>;
const int mod = 998244353;
int n;
//第 i 个字母 状态为 j 的操作次数
//dp[i][j] = dp[i-1][k]ll a[200050];
ll dp[200050][8];//x y z
ll x,y,z,xy,xz,yz,xyz;ll calc(ll h, int cur , int pre){//1 0//0 1//0 1int g[3] = {0,0,0};for(int i = 0 ; i <= 2 ; i++){if((cur>>i) & 1 && ((pre>>i) & 1) == 0){g[i] = 1;}}ll t;//3 4//if(g[0] == 0 && g[1] == 0 && g[2] == 0){t = 0;}else if(g[0] == 1 && g[1] == 0 && g[2] == 0){t = x - h % x;t %= x;}else if(g[0] == 1 && g[1] == 1 && g[2] == 0){t = xy - h % xy;t %= xy;}else if(g[0] == 1 && g[1] == 1 && g[2] == 1){t = xyz - h % xyz;t %= xyz;}else if(g[0] == 0 && g[1] == 1 && g[2] == 0){t = y - h % y;t %= y;}else if(g[0] == 0 && g[1] == 1 && g[2] == 1){t = yz - h % yz;t %= yz;}else if(g[0] == 0 && g[1] == 0 && g[2] == 1){t = z - h % z;t %= z;}else if(g[0] == 1 && g[1] == 0 && g[2] == 1){t = xz - h % xz;t %= xz;}return t;}int main(){cin>>n>>x>>y>>z;xy = x * y / __gcd(x,y);xz = x * z / __gcd(x,z);yz = z * y / __gcd(z,y);xyz = xy * z / __gcd(xy,z);for(int i = 1 ; i <= n ; i++) cin>>a[i];for(int i = 0 ; i <= n ; i++){for(int j = 0 ; j <= 7 ; j++){dp[i][j] = 1e18;}dp[i][0] = 0;}for(int i = 1 ; i <= n ; i++){for(int j = 0 ; j <= 7 ; j++){for(int k = 0 ; k <= 7 ; k++){dp[i][j] = min(dp[i][j] , dp[i-1][k] + calc(a[i] , j , k));}}}/* cout<<calc(8 , 2 , 0);cout<<dp[1][2];*/cout<<dp[n][7];}和网络赛没做出来的dp挺像的
类似就是状态枚举 ， 考虑每个状态的花费 ， 然后直接转移
这篇关于arc 166 b的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
