【C++动态规划】B3734 [信息与未来 2017] 加强版密码锁|普及+

本文涉及知识点

C++动态规划

B3734 [信息与未来 2017] 加强版密码锁

题目描述

乌龟偶然获得了一个宝箱，宝箱上又有一把密码锁。密码锁由n nn个拨盘组成，每个拨盘初始时有一个0 00到
99 9999之间的整数。向上拨使数字x xx变为( x + 1 ) m o d 100 (x+1) \bmod 100(x+1)mod100，
向下拨使数字x xx变为( x + 99 ) m o d 100 (x+99) \bmod 100(x+99)mod100。

因为密码锁年久失修，拨盘拨动的次数越多越费力。
如果一个拨盘被拨动k kk次，需要花费k 2 k^2k2单位时间。

密码锁只有在所有的拨盘上的数字形成一个从左到
右严格递增的数列时才会解开。乌龟再次请你帮忙，求
解解开密码锁的最少时间。

试题中使用的生成数列R RR定义如下：整数0 ≤ R 1 < 201701 0\leq R_1\lt 2017010≤R1​<201701在输入中给出。

对于i > 1 , R i = ( R i − 1 × 6807 + 2831 ) m o d 201701 i\gt 1,R_i=(R_{i−1}\times 6807+2831)\bmod 201701i>1,Ri​=(Ri−1​×6807+2831)mod201701。

输入格式

两个整数n , R 1 n,R_1n,R1​，表示拨盘的数量和数列生成的首项。从左向右数第i ( 1 ≤ i ≤ n ) i(1\leq i\leq n)i(1≤i≤n)个拨盘的初始数字为R i m o d 100 R_i \bmod 100Ri​mod100。

输出格式

一个整数，表示解开密码锁的最少时间。

输入输出样例 #1

输入 #1

10 4

输出 #1

3338

说明/提示

30 % 30\%30%的数据满足n ≤ 3 n\leq3n≤3，所有数据满足1 ≤ n ≤ 100 1\leq n\leq 1001≤n≤100。

本题原始满分为20 pts 20\text{pts}20pts。

B3734 动态规划

动态规划的状态表示

dp[i][j]表示前i+1个锁盘严格升序，第i个（下标从0开始）锁盘j的最小成本数。 空间复杂度：O(∑ \sum∑N),∑ \sum∑是锁盘的可选值，本题是100。可以用滚动向量优化空间复杂度。

动态规划的填表顺序

枚举前置状态, i =1 to N-1 j = 0 to 99 j2= j+1 to 99

动态规划的转移方程

如果j2=j，增加的成本是0。
如果j2 > j，顺时针旋转 j2-j,逆时针旋转100-(j2-j)。
如果j2 < j，j2和j互换后，和j2>j同。
总结：k = min(abs(j2-j),100-abs(j2-j))，增加的成本是kk。
单个状态时间复杂度：O(∑ \sum∑)，总时间复杂度：O(n∑ ∑ \sum\sum∑∑)

动态规划的初始值

dp[0]要单独计算。

动态规划的返回值

min(pre)

可以利用前缀和优化

枚举后置状态，dp[j2] = min(pre[0…j2-1])+本次的成本。时间复杂度：O(n∑ \sum∑)

代码

核心代码

#include<iostream>#include<sstream>#include<vector>#include<map>#include<unordered_map>#include<set>#include<unordered_set>#include<string>#include<algorithm>#include<functional>#include<queue>#include<stack>#include<iomanip>#include<numeric>#include<math.h>#include<climits>#include<assert.h>#include<cstring>#include<list>#include<bitset>usingnamespacestd;template<classT1,classT2>std::istream&operator>>(std::istream&in,pair<T1,T2>&pr){in>>pr.first>>pr.second;returnin;}template<classT1,classT2,classT3>std::istream&operator>>(std::istream&in,tuple<T1,T2,T3>&t){in>>get<0>(t)>>get<1>(t)>>get<2>(t);returnin;}template<classT1,classT2,classT3,classT4>std::istream&operator>>(std::istream&in,tuple<T1,T2,T3,T4>&t){in>>get<0>(t)>>get<1>(t)>>get<2>(t)>>get<3>(t);returnin;}template<classT=int>vector<T>Read(){intn;scanf("%d",&n);vector<T>ret(n);for(inti=0;i<n;i++){cin>>ret[i];}returnret;}template<classT=int>vector<T>Read(intn){vector<T>ret(n);for(inti=0;i<n;i++){cin>>ret[i];}returnret;}template<intN=1'000'000>classCOutBuff{public:COutBuff(){m_p=puffer;}template<classT>voidwrite(T x){intnum[28],sp=0;if(x<0)*m_p++='-',x=-x;if(!x)*m_p++=48;while(x)num[++sp]=x%10,x/=10;while(sp)*m_p++=num[sp--]+48;AuotToFile();}voidwritestr(constchar*sz){strcpy(m_p,sz);m_p+=strlen(sz);AuotToFile();}inlinevoidwrite(charch){*m_p++=ch;AuotToFile();}inlinevoidToFile(){fwrite(puffer,1,m_p-puffer,stdout);m_p=puffer;}~COutBuff(){ToFile();}private:inlinevoidAuotToFile(){if(m_p-puffer>N-100){ToFile();}}charpuffer[N],*m_p;};template<intN=1'000'000>classCInBuff{public:inlineCInBuff(){}inlineCInBuff<N>&operator>>(char&ch){FileToBuf();ch=*S++;return*this;}inlineCInBuff<N>&operator>>(int&val){FileToBuf();intx(0),f(0);while(!isdigit(*S))f|=(*S++=='-');while(isdigit(*S))x=(x<<1)+(x<<3)+(*S++^48);val=f?-x:x;S++;//忽略空格换行return*this;}inlineCInBuff&operator>>(longlong&val){FileToBuf();longlongx(0);intf(0);while(!isdigit(*S))f|=(*S++=='-');while(isdigit(*S))x=(x<<1)+(x<<3)+(*S++^48);val=f?-x:x;S++;//忽略空格换行return*this;}template<classT1,classT2>inlineCInBuff&operator>>(pair<T1,T2>&val){*this>>val.first>>val.second;return*this;}template<classT1,classT2,classT3>inlineCInBuff&operator>>(tuple<T1,T2,T3>&val){*this>>get<0>(val)>>get<1>(val)>>get<2>(val);return*this;}template<classT1,classT2,classT3,classT4>inlineCInBuff&operator>>(tuple<T1,T2,T3,T4>&val){*this>>get<0>(val)>>get<1>(val)>>get<2>(val)>>get<3>(val);return*this;}template<classT=int>inlineCInBuff&operator>>(vector<T>&val){intn;*this>>n;val.resize(n);for(inti=0;i<n;i++){*this>>val[i];}return*this;}template<classT=int>vector<T>Read(intn){vector<T>ret(n);for(inti=0;i<n;i++){*this>>ret[i];}returnret;}private:inlinevoidFileToBuf(){constintcanRead=m_iWritePos-(S-buffer);if(canRead>=100){return;}if(m_bFinish){return;}for(inti=0;i<canRead;i++){buffer[i]=S[i];//memcpy出错}m_iWritePos=canRead;buffer[m_iWritePos]=0;S=buffer;intreadCnt=fread(buffer+m_iWritePos,1,N-m_iWritePos,stdin);if(readCnt<=0){m_bFinish=true;return;}m_iWritePos+=readCnt;buffer[m_iWritePos]=0;S=buffer;}intm_iWritePos=0;boolm_bFinish=false;charbuffer[N+10],*S=buffer;};classSolution{public:intAns(constintN,intr1){vector<int>rs={r1};for(inti=1;i<N;i++){rs.emplace_back((rs.back()*6807LL+2831)%201701);}for(auto&i:rs){i=i%100;}vector<int>pre(100,1e8);for(intj2=0;j2<100;j2++){constintt=abs(j2-rs[0]);constintk=min(t,100-t);pre[j2]=k*k;}for(inti=1;i<N;i++){vector<int>cur(100,1e8);for(intj=0;j<100;j++){for(intj2=j+1;j2<100;j2++){constintt=abs(j2-rs[i]);constintk=min(t,100-t);cur[j2]=min(cur[j2],pre[j]+k*k);}}pre.swap(cur);}return*min_element(pre.begin(),pre.end());}};intmain(){#ifdef_DEBUGfreopen("a.in","r",stdin);#endif// DEBUGintn,r1;cin>>n>>r1;#ifdef_DEBUG//printf("N=%d,", N);//Out(mat, ",mat=");//Out(pos, ",pos=");/*Out(edge, "edge="); Out(que, "que=");*/#endif// DEBUGautores=Solution().Ans(n,r1);cout<<res;return0;}