A32888. 加强版密码锁程序文件名：t6.cpp输入文件名：t6.in输出文件名：t6.out。乌龟偶然获得了一个宝箱，宝箱上又有一把密码锁。密码锁由n 个拨盘组成，每个拨盘初始时有一个0 到99 之间的整数。向上拨使数字x 变为(x+1) mod 100，向下拨使数字x 变为(x + 99) mod 100。因为密码锁年久失修，拨盘拨动的次数越多越费力。如果一个拨盘被拨动k 次，需要花费k^2 单位时间。…
填空题
困难
知识点
题目描述
加强版密码锁
程序文件名：t6.cpp
输入文件名：t6.in
输出文件名：t6.out。
乌龟偶然获得了一个宝箱，宝箱上又有一把密码锁。密码锁由n 个拨盘组成，每个拨盘初始时有一个0 到99 之间的整数。向上拨使数字x 变为(x+1) mod 100，向下拨使数字x 变为(x + 99) mod 100。
因为密码锁年久失修，拨盘拨动的次数越多越费力。如果一个拨盘被拨动k 次，需要花费k^2 单位时间。
密码锁只有在所有的拨盘上的数字形成一个从左到右严格递增的数列时才会解开。乌龟再次请你帮忙，求解解开密码锁的最少时间。
输入
两个整数n, R1，表示拨盘的数量和数列生成的首项。从左向右数第i (1 <= i <= n) 个拨盘的初始数字为Ri mod 100
输出
一个整数，表示解开密码锁的最少时间
样例输入
10 4
样例输出
3338
数据规模
30% 的数据满足n <= 3，所有数据满足1 <= n <= 100
参考答案
#include<bits/stdc++.h>
using namespace std;
int a[1010],r[1010],dp1[110][110],dp[110][110];
int n,ans,tot,ma;
void init()
{
cin>>n>>r[1];
for(int i=1;i<=n;++i){
a[i]=r[i]%100;
r[i+1]=(r[i]*6807+2831)%201701;
}
}
int check(int i,int j)
{
int mi=100;
mi=min(mi,abs(a[i]-j));
mi=min(mi,abs(a[i]+100-j));
mi=min(mi,abs(j+100-a[i]));
return mi*mi;
}
int main()
{
freopen("t6.in","r",stdin);
freopen("t6.out","w",stdout);
int i,j,k,ans=1<<30;
init();
for(i=1;i<=n;++i){
for(j=0;j<=99;++j){
dp[i][j]=2000000;
dp1[i][j]=check(i,j);
}
}
for(j=0;j<=99;++j)
dp[1][j]=dp1[1][j];
for(i=2;i<=n;++i)
for(j=0;j<=99;++j)
for(k=0;k<j;++k)
dp[i][j]=min(dp[i][j],dp[i-1][k]+dp1[i][j]);
for(j=0;j<=99;++j)
ans=min(ans,dp[n][j]);
cout<<ans;
fclose(stdin);fclose(stdout);
return 0;
}
上一题
下一题