赞
踩
题目描述
xiaok大佬最近再雇佣工人给他掰木棒。把一根长为L的木棒锯成两段,他需要支付给工人L元钱。xiaok大佬一开始只有长为L的一根木棒,他想把它锯成n段,每段长度分别为L1,L2,…,Ln,问xiaok大佬最少要付给工人多少钱?
输入
第一行两个整数n,L(1<n<103,n<L<109)
第二行n个整数L1,L2,…,Ln(0<Li<L,且保证L1+L2+…+Ln=L)
输出
输出一个整数,表示最小花费
**样例输入 **
3 21
8 5 8
样例输出
34
Code
#include<bits/stdc++.h> using namespace std; int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("锯木棒.in","r",stdin); // freopen("锯木棒.ans","w",stdout); //begin code int n,L; cin>>n>>L; priority_queue<int, vector<int>, greater<int> > pL; //这样就是小顶堆 int Li; int min_money=0; for(int i=0;i<n;i++){ cin>>Li; pL.push(Li); } while(pL.size()>1){ int t1=pL.top();pL.pop(); int t2=pL.top();pL.pop(); int t3=t1+t2; min_money+=t3; pL.push(t3); } cout<<min_money<<endl; //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad" ,顺次选1,3,5个字符就构成子串" cad" ,现给定两个字符串,求它们的最长共公子串。
输入
第一行两个字符串用空格分开。两个串的长度均小于2000 。
输出
最长子串的长度。
样例输入
abccd aecd
样例输出
3
Code
#include<bits/stdc++.h> using namespace std; int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("最长公共子序列.in","r",stdin); // freopen("最长公共子序列.ans","w",stdout); //begin code string A,B; cin>>A; cin>>B; int x = A.length(); int y = B.length(); A = ' ' + A; B = ' ' + B; int i, j; int ** LCS = new int*[x+1]; for(i=0;i<=x;i++) { LCS[i] = new int[y+1]; for (j=0;j<=y;j++) LCS[i][j] = 0; //LCS[i][j]用来存储 } for(i=0;i<=x;i++) for(j=0;j<=y;j++) if(i==0 || j==0) LCS[i][j] = 0; else { if(A[i] == B[j]) LCS[i][j] = LCS[i-1][j-1] + 1; else LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]); } int result = LCS[x][y]; cout << result << endl; //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
给定n个矩阵{A1,A2,…,An},及m个矩阵连乘的表达式,判断每个矩阵连乘表达式是否满足矩阵乘法法则,如果满足,则计算矩阵的最小连乘次数,如果不满足输出“MengMengDa“。
输入
输入数据由多组数据组成(不超过10组样例)。每组数据格式如下:
第一行是2个整数n (1≤n≤26)和m(1≤m≤3),表示矩阵的个数。
接下来n行,每行有一个大写字母,表示矩阵的名字,后面有两个整数r和c,分别表示该矩阵的行数和列数,其中1<r, c<100。
第n+1行到第n+m行,每行是一个矩阵连乘的表达式(2<=矩阵个数<=100)。
输出
对于每个矩阵连乘表达式,如果运算不满足矩阵乘法法则的情况(即左矩阵列数与右矩阵的行数不同),则输出“MengMengDa”,否则输出最小矩阵连乘次数。
数据保证结果不超过1e9。
样例输入
3 2
A 10 100
B 5 50
C 100 5
ACB
ABC
样例输出
7500
MengMengDa
Code
#include<bits/stdc++.h> typedef long long ll; using namespace std; class Matrix { public: char name; int row,col; Matrix(char name='\0',int row=0,int col=0):name(name),row(row),col(col) { } void reset(char name,int row,int col) { this->name=name; this->row=row; this->col=col; } void print() { cout<<"matrix "<<name<<" row="<<row<<" col="<<col<<endl; } }; class MatrixVector { public: int num; Matrix* mats; MatrixVector(int num):num(num) { mats=new Matrix[num]; } Matrix find(char alpha) { for(int i=0; i<num; i++) { if(mats[i].name==alpha) { return mats[i]; } } } }; void MatrixChain(vector<int> p,int n) { ll** m=new ll*[n+1]; int** s=new int*[n+1]; for(int i=0; i<=n; i++) { m[i]=new ll[n+1]; s[i]=new int[n+1]; } for(int i=1; i<=n; i++) { m[i][i]=0; } for(int r=2; r<=n; r++) { for(int i=1; i<=n-r+1; i++) { int j=i+r-1; m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i; for(int k=i+1; k<j; k++) { int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(t<m[i][j]) { m[i][j]=t; s[i][j]=k; } } } } cout<<m[1][n]<<endl; } int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("矩阵连乘.in","r",stdin); // freopen("矩阵连乘.ans","w",stdout); //begin code int n,m; while(cin>>n>>m) { MatrixVector mv(n); char name; int row,col; for(int i=0; i<n; i++) { cin>>name>>row>>col; mv.mats[i].reset(name,row,col); } string str=""; vector<vector<int>> v; vector<int> len; vector<bool> flag; for(int i=0; i<m; i++) { str=""; cin>>str; bool flag_i=true; vector<int> p; Matrix mat=mv.find(str[0]); p.push_back(mat.row); p.push_back(mat.col); for(int j=1; j<str.length(); j++) { mat=mv.find(str[j]); if(p.back()!=mat.row) { flag_i=false; break; } else { p.push_back(mat.col); } } v.push_back(p); len.push_back(str.length()); flag.push_back(flag_i); } for(int i=0; i<m; i++) { if(flag[i]==true) { MatrixChain(v[i],len[i]); } else { cout<<"MengMengDa"<<endl; } } } //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
设有N堆沙子排成一排,其编号为1,2,3,…,N(N< =300)。每堆沙子有一定的数量,可以用一个整数来描述,现在要将N堆沙子合并成为一堆,每次只能合并相邻的两堆,合并的代价为这两堆沙子的数量之和,合并后与这两堆沙子相邻的沙子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同,如有4堆沙子分别为1 3 5 2我们可以先合并1、2堆,代价为4,得到4 5 2又合并1,2堆,代价为9,得到9 2,再合并得到11,总代价为4+9+11=24,如果第二步是先合并2,3堆,则代价为7,得到4 7,最后一次合并代价为11,总代价为4+7+11=22;问题是:找出一种合理的方法,使总的代价最小。输出最小代价。
输入
第一行一个数N表示沙子的堆数N。 第二行N个数,表示每堆沙子的质量。 a[i]< =1000。
输出
合并的最小代价。
样例输入
4
1 3 5 2
样例输出
22
Code
#include<bits/stdc++.h> typedef long long ll; using namespace std; void MatrixChain(vector<int> p,int n) { ll** m=new ll*[n+1]; int** s=new int*[n+1]; int* preSum=new int[n+1]; preSum[0]=0; for(int i=1;i<n+1;i++){ preSum[i]=preSum[i-1]+p[i-1]; } for(int i=0; i<=n; i++) { m[i]=new ll[n+1]; s[i]=new int[n+1]; } for(int i=1; i<=n; i++) { m[i][i]=0; } for(int r=2; r<=n; r++) { for(int i=1; i<=n-r+1; i++) { int j=i+r-1; m[i][j]=m[i][i]+m[i+1][j]+preSum[j]-preSum[i-1]; s[i][j]=i; for(int k=i+1; k<j; k++) { int t=m[i][k]+m[k+1][j]+preSum[j]-preSum[i-1]; if(t<m[i][j]) { m[i][j]=t; s[i][j]=k; } } } } cout<<m[1][n]<<endl; } int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("沙子的质量.in","r",stdin); // freopen("沙子的质量.ans","w",stdout); //begin code int n; cin>>n; vector<int> v; for(int i=0;i<n;i++){ int temp; cin>>temp; v.push_back(temp); } MatrixChain(v,n); //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
给定n(1<=n<=1000000)个元素,求第k小数(1<=k<=n)。
输入
一组样例。第一行输入两个整数n和k。第二行输入n个不同的int范围内的数。
输出
输出一行,输出第k小数。
样例输入
5 2
1 5 3 2 4
样例输出
2
Code
#include<bits/stdc++.h> typedef long long ll; using namespace std; int partition(int a[], int left, int right) {//将数组a的第left到right个元素进行划分 int x = a[left]; while (left < right) {//采用快排策略 while (left < right && a[right] >= x) right--; a[left] = a[right]; while (left < right && a[left] <= x) left++; a[right] = a[left]; } a[left] = x; return left; } int find(int a[], int left, int right, int k) {//在数组a的第left到right中寻找第k小的数 int pos = partition(a, left, right); if (k - 1 == pos) cout << a[k - 1]; else if (k - 1 < pos)//判断下一次划分在哪一区间进行 find(a, left, pos - 1, k); else find(a, pos + 1, right, k); return 0; } int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("求第k小.in","r",stdin); // freopen("求第k小.ans","w",stdout); //begin code int n, k; cin >> n >> k; int a[1000000]; for (int i = 0; i < n; i++) cin >> a[i]; find(a, 0, n - 1, k); //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
给定x,求f(x)对100000007取余的结果。
输入
多组测试样例,最多50组。每组测试样例给定一个整数x(1<=x<=25000)
输出
对每个样例,输出一行,代表f(x)对100000007取余的结果。
样例输入
3
4
5
样例输出
33
289
3414
Code
#include<bits/stdc++.h> typedef long long ll; using namespace std; const long long tmp = 100000007; // 对它取余 ll fastPower(ll base, ll power) { long long result = 1; while (power > 0) { if (power & 1) {//此处等价于if(power%2==1) 二进制最后一位与1相与 result = result * base % tmp; } power >>= 1;//此处等价于power=power/2 ,对二进制右移一位 base = (base * base) % tmp; } return result; } int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("快速幂.in","r",stdin); // freopen("快速幂.ans","w",stdout); //begin code ll x; while(cin>>x){ ll sum = 0; for(ll i=1;i<=x;i++){ sum += fastPower(i, i); sum %= tmp; } cout<<sum + 1<<endl; } //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
输入一个可能含有重复字符的字符串,打印出该字符串中所有字符的全排列。
输入
单组测试数据,输入数据是一个长度不超过10个字符的字符串,以逗号结尾。
输出
打印出该字符串中所有字符的全排列。以字典序顺序输出,用空格分隔。
样例输入
abc,
样例输出
abc acb bac bca cab cba
Code
#include<bits/stdc++.h> typedef long long ll; using namespace std; void swap(char& x,char& y) { char t=x; x=y; y=t; } void sort(string &arr,int begin,int end) { int i,j; for(i=begin; i<=end; i++) { for(j=i+1; j<=end; j++) { if(arr[i]>arr[j]) { swap(arr[i],arr[j]); } } } } void permutation(string &s,int start,int end) { if(start==end) { cout<<s<<" "; } else { for(int i=start; i<=end; i++) { swap(s[start],s[i]); sort(s,start+1,end); permutation(s,start+1,end); sort(s,start+1,end); } } } int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("排列问题.in","r",stdin); // freopen("排列问题.ans","w",stdout); //begin code string s; cin>>s; s.erase(s.length()-1); sort(s,0,s.length()-1); permutation(s,0,s.length()-1); //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
输入一个十进制正整数,然后输出它所对应的八进制数。
输入
输入一个十进制正整数n(1≤n≤106) 。
输出
输出n对应的八进制数,输出在一行。
样例输入
10
样例输出
12
Code
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("进制转换.in","r",stdin); // freopen("进制转换.ans","w",stdout); //begin code ll x; cin>>x; vector<int> v; while(x){ v.push_back(x%8); x/=8; } for(auto i=v.end()-1;i>=v.begin();i--){ cout<<*i; } //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
农历新年马上就要到了,奶牛们计划举办一次聚会庆祝新年的到来。但是,奶牛们并不喜欢走太远的路,这会给他们的聚会带来消极情绪,当一头奶牛的消极指数为Wi,他参加聚会所需行走的距离为si,那么他就会给聚会带来Si3*Wi的消极情绪。所有奶牛所在位置都在一条直线上,已知所有奶牛的坐标和消极指数,求如何确定聚会地点,使得所有奶牛给聚会带来的消极情绪之和最小,输出消极情绪之和的最小值。
输入
第一行包含一个整数 Ca(Ca<=20) ,表示有 Ca 组测试数据。
对于每组测试数据:第一行包含一个整数n(1<=n<=50000) ,表示奶牛的数量。接下来 n 行每行包含两个浮点数Si和wi (-106<=Si<=106, 0<Wi<15)。
输出
对于每组测试数据,输出 “Case #c: ans” ,其中c表示测试数据编号,ans表示消极情绪之和的最小值,结果四舍五入为一个整数。
样例输入
1
5
0.9 2
1.4 4
3.1 1
6.2 1
8.3 2
样例输出
Case #1: 300
Code
#include<bits/stdc++.h> typedef long long ll; using namespace std; vector<double> X,W; int n; double F(double t){ double sum = 0; for(int i=0;i<n;i++){ sum += pow(abs(X[i]-t), 3)*W[i]; } return sum; } int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("奶牛的聚会.in","r",stdin); // freopen("奶牛的聚会.ans","w",stdout); //begin code int ca; cin>>ca; int cur=ca; while(cur--){ cin>>n; X.clear(); W.clear(); double L=1e6,R=-1e6; for(int i=0;i<n;i++){ double xi,wi; cin>>xi>>wi; L=min(xi,L);//L表示坐标的最小者 R=max(xi,R);//R表示坐标的最大值 X.push_back(xi); W.push_back(wi); } while(R-L>1e-6){ double x1 = L + (R-L)/3.0; // x1取 [L, R]区间的1/3 点 double x2 = R - (R-L)/3.0; // x2取 [L, R]区间的2/3 点 if(F(x1) > F(x2)) L = x1; // 若x1点的情绪之和较大, 则x1替换L else R= x2; } cout<<"Case #"<<ca-cur<<": "<< ll(F(L) + 0.5)<<endl; } //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
输入
多组测试样例。每组测试样例包含一个整数n。(1<=n<=100)
输出
每组测试样例输出一行,表示青蛙跳上n级台阶的跳法数量.
所得到的结果模1000000007
样例输入
3
4
样例输出
3
5
Code
#include<bits/stdc++.h> typedef long long ll; using namespace std; vector<int> ans; int tmp=1000000007; int F(int n){ if(n==0){ return 0; }else if(n==1){ return 1; }else if(n==2){ return 2; }else{ int f1=1,f2=2,t; for(int i=0;i<n-2;i++){ t=f2; f2=(f1+f2)%tmp; f1=t; } return f2; } } int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("跳台阶.in","r",stdin); // freopen("跳台阶.ans","w",stdout); //begin code int n; while(cin>>n){ // ans.push_back(F(n)); cout<<F(n)<<endl; } //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
你来到一个迷宫前。该迷宫由若干个房间组成,每个房间都有一个得分,第一次进入这个房间,你就可以得到这个分数。还有若干双向道路连结这些房间,你沿着这些道路从一个房间走到另外一个房间需要一些时间。游戏规定了你的起点和终点房间,你首要目标是从起点尽快到达终点,在满足首要目标的前提下,使得你的得分总和尽可能大。现在问题来了,给定房间、道路、分数、起点和终点等全部信息,你能计算在尽快离开迷宫的前提下,你的最大得分是多少么?
输入
第一行4个整数n (<=500), m, start, end。n表示房间的个数,房间编号从0到(n - 1),m表示道路数,任意两个房间之间最多只有一条道路,start和end表示起点和终点房间的编号。
第二行包含n个空格分隔的正整数(不超过600),表示进入每个房间你的得分。
再接下来m行,每行3个空格分隔的整数x, y, z (0<z<=200)表示道路,表示从房间x到房间y(双向)的道路,注意,最多只有一条道路连结两个房间,你需要的时间为z。
输入保证从start到end至少有一条路径。
输出
占一行,分别最短时间和相应的最大得分,中间用空格隔开。
样例输入
3 2 0 2
1 2 3
0 1 10
1 2 11
样例输出
21 6
Code
#include<iostream> using namespace std; typedef long long ll; int inf=0x7fffffff; int* value;//不同房间的价值 int** distence;//不同房间之间的时间 int* score;//start到i的得分 int* length;//start到i的长度 bool* flag;//第i个点是否经过 int n,m,st,en;//房间数,通道数,起点房间,终点房间 void dijsk() { //初始化score[] for(int i=0; i<n; i++) { length[i]=distence[st][i]; if(st!=i) { score[i]=value[st]+value[i]; } else { score[i]=value[st]; } } flag[st]=true; //开始循环 for(int i=0; i<n; i++) { int tmp=inf; int id=-1;; for(int j=0; j<n; j++) { if(!flag[j]&&tmp>length[j]) { tmp=length[j]; id=j; } } if(id==-1)break; flag[id]=true; for(int k=0; k<n; k++) { if(k==id)continue; if(length[k]>length[id]+distence[id][k]) { length[k]=length[id]+distence[id][k]; score[k]=score[id]+value[k]; } else if(length[k]==length[id]+distence[id][k]) { if(score[k]<score[id]+value[k]) { score[k]=score[id]+value[k]; } } } } cout<<length[en]<<" "<<score[en]<<endl; } int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("迷宫游戏.in","r",stdin); // freopen("迷宫游戏.ans","w",stdout); //begin code while(cin>>n>>m>>st>>en) { value=new int [n]; flag=new bool[n]; distence =new int*[n]; score=new int[n]; length=new int[n]; for(int i=0; i<n; i++) { cin>>value[i]; flag[i]=false; distence[i]=new int[n]; for(int j=0; j<n; j++) { distence[i][j]=inf; } distence[i][i]=0; } for(int i=0; i<m; i++) { int x,y,t; cin>>x>>y>>t; distence[x][y]=t; distence[y][x]=t; } dijsk(); } //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
临近开学了,大家都忙着收拾行李准 备返校,但 I_Love_C 却不为此担心! 因为他的心思全在暑假作业上:目前为止还未开动。
暑假作业是很多张试卷,我们这些从试卷里爬出来的人都知道,卷子上的题目有选择题、填空题、简答题、证明题等。而做选择题的好处就在于工作量很少,但又因为选择题题目都普遍很长。如果有 5 张试卷,其中 4 张是选择题,最后一张是填空题,很明显做最后一张所花的时间要比前 4 张长很多。但如果你只做了选择题,虽然工作量很少,但表面上看起来也已经做了4/5的作业了。
I_Love_C决定就用这样的方法来蒙混过关,他统计出了做完每一张试卷所需的时间以及它做完后能得到的价值(按上面的原理,选择题越多价值当然就越高咯)。
现在就请你帮他安排一下,用他仅剩的一点时间来做最有价值的作业。
输入
测试数据包括多组。每组测试数据以两个整数 M,N(1<M<20,1<N<10000) 开头,分别表示试卷的数目和 I_Love_C 剩下的时间。接下来有 M 行,每行包括两个整数 T,V(1<T<N,1<V<10000)分别表示做完这张试卷所需的时间以及做完后能得到的价值,输入以 0 0 结束。
输出
对应每组测试数据输出 I_Love_C 能获得的最大价值。保留小数点 2 位
提示:float 的精度可能不够,你应该使用 double 类型。
样例输入
4 20
4 10
5 22
10 3
1 2
0 0
样例输出
37.00
Code
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct homework{ double time; double value; double ratio; }; int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("Homework.in","r",stdin); // freopen("Homework.ans","w",stdout); //begin code vector<homework> work; int M,N; while(cin>>M>>N){ if(M==0&&N==0) break; work.resize(M); for(int i=0;i<M;i++){ cin>>work[i].time>>work[i].value; work[i].ratio=work[i].value/work[i].time; } sort(work.begin(),work.end(),[](const homework& a,const homework& b){ return (a.ratio>b.ratio); }); double sum=0.0; int c=N; for(int i=0;i<M;i++){ if(c>work[i].time){ sum+=work[i].value; c-=work[i].time; }else{ sum+=c*work[i].ratio; break; } } cout<<fixed<<setprecision(2)<<sum<<endl; //输出两位小数 } //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
给定一只含有小写字母的字符串;输出其哈夫曼编码的长度
输入
第一行一个整数T,代表样例的个数,接下来T行,每行一个字符串,0<T<=2000,字符串长度0<L<=1500.
输出
对于每个字符串,输出其哈夫曼编码长度
样例输入
3
hrvsh
lcxeasexdphiopd
mntflolfbtbpplahqolqykrqdnwdoq
样例输出
10
51
115
Code
#include<bits/stdc++.h> using namespace std; priority_queue<int,vector<int>,greater<int>> q; int alpha[26]; void huffman(){ while(!q.empty()){ q.pop(); } for(int i=0;i<26;i++){ if(alpha[i]){ q.push(alpha[i]); } } int sum=0; while(q.size()>1){ int x=q.top(); q.pop(); int y=q.top(); q.pop(); q.push(x+y); sum+=x+y; } cout<<sum<<endl; } int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("哈夫曼编码.in","r",stdin); // freopen("哈夫曼编码.ans","w",stdout); //begin code int T; cin>>T; while(T--){ string s; cin>>s; memset(alpha,0,sizeof(alpha)); for(char c:s){ alpha[c-'a']++; } huffman(); } //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如下表就是一个费用的单子。没有一辆车子行驶超过10公里,一个顾客打算行驶n公里(1<=n<100),它可以通过无限次的换车来完成旅程。最后要求费用最少。
输入
第一行十个整数分别表示行走1到10公里的费用(<=500)。注意这些数并无实际的经济意义,即行驶10公里费用可能比行驶一公里少。第二行一个整数n表示,旅客的总路程数。
输出
仅一个整数表示最少费用。
样例输入
12 21 31 40 49 58 69 79 90 101
15
样例输出
147
Code
#include<bits/stdc++.h> using namespace std; const int inf=0x7fffffff; int cost[100]; int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("汽车费用.in","r",stdin); // freopen("汽车费用.ans","w",stdout); //begin code memset(cost,-1,sizeof(cost)); cost[0]=0; for(int i=1;i<=10;i++){ cin>>cost[i]; } int n; cin>>n; for(int i=2;i<=10;i++){ int min_cost=cost[i]; for(int j=1;j<i/2+1;j++){ min_cost=min(min_cost,cost[j]+cost[i-j]); } cost[i]=min_cost; } for(int i=11;i<=n;i++){ int min_cost=inf; for(int j=1;j<i/2+1;j++){ min_cost=min(min_cost,cost[j]+cost[i-j]); } cost[i]=min_cost; } cout<<cost[n]<<endl; //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
努比亚和苏丹没有子女,所以他要从一些有集成资格的继承者中挑选一个出来继承王位。他希望这个继承者足够聪明,所以他准备了一个西洋棋盘,上面的每个格子中均有一个 1-99 的数字。他又准备了 8 个皇后棋子。
8 皇后的规则就是不能有任何棋子同行或者同列或者同斜线,在满足这个规则的同时,王位继承者还需要让 8 个皇后所在的位置的数字的和是最大的。
输入
输入一个数字 k(k≤20),代表棋盘的数量。
接下来有 k 个棋盘,每个棋盘有 64 个数字,分成 8 行 8 列输入,具体可见样例,每一个数字均小于 100。
输出
每一个棋盘对应输出最大的数值, 一共输出 k行
样例输入
1
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
样例输出
260
Code
#include<bits/stdc++.h> using namespace std; int y[8]; int board[8][8]; int flag[3][15]; int MAX; const int _inf=0x80000000; void DFS(int i) { if(i>=8) { int sum=0; for(int j=0; j<8; j++) { sum+=board[j][y[j]]; } if(sum>MAX) { MAX=sum; } } else { for(int j=0; j<8; j++) { if(!flag[0][j]&&!flag[1][i+j]&&!flag[2][i-j+7]) { y[i]=j; flag[0][j]=flag[1][i+j]=flag[2][i-j+7]=true; DFS(i+1); flag[0][j]=flag[1][i+j]=flag[2][i-j+7]=false; } } } } int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("八皇后问题.in","r",stdin); // freopen("八皇后问题.ans","w",stdout); //begin code int k; cin>>k; while(k--) { MAX=_inf; memset(flag,0,sizeof(flag)); memset(y,-1,sizeof(y)); for(int i=0; i<8; i++) { for(int j=0; j<8; j++) { cin>>board[i][j]; } } DFS(0); cout<<MAX<<endl; } //end code // fclose(stdin); // fclose(stdout); return 0; }
题目描述
三个法师康的工人每天早上6点到工厂开始到三条产品生产线上组装桔子手机。第一个工人在200时刻开始(从6点开始计时,以秒作为单位)在生产线上开始生产,一直到1000时刻。第二个工人,在700时刻开始,在1100时刻结束。第三个工人从1500时刻工作到2100时刻。期间最长至少有一个工人在生产线上工作的连续时间为900秒(从200时刻到1100时刻),而最长的无人生产的连续时间(从生产开始到生产结束)为400时刻(1100时刻到1500时刻)。
你的任务是用一个程序衡量N个工人在N条产品线上的工作时间列表(1≤N≤5000,以秒为单位)。
·最长的至少有一个工人在工作的时间段
·最长的无人工作的时间段(从有人工作开始计)
输入
输入第1行为一个整数N,第2-N+1行每行包括两个均小于1000000的非负整数数据,表示其中一个工人的生产开始时间与结束时间。
输出
输出为一行,用空格分隔开两个我们所求的数。
样例输入
3
200 1000
700 1100
1500 2100
样例输出
900 400
Code
合并有重叠时间的工人
#include<bits/stdc++.h> using namespace std; struct worker { int st; int en; int dur; }; vector<worker> v; bool canMerge(const worker& w1,const worker& w2) { // cout<<"调用合并判断"<<endl; if(w1.st<=w2.st&&w2.st<=w1.en&&w1.en<=w2.en|| w2.st<=w1.st&&w1.st<=w2.en&&w2.en<=w1.en|| w1.st<=w2.st&&w1.en>=w2.en|| w1.st>=w2.st&&w1.en<=w2.en) { // cout<<"可以合并"<<endl; return true; } else { // cout<<"不可以合并"<<endl; return false; } } worker merge(worker w1,worker w2) { worker w3; w3.st=w1.st<w2.st?w1.st:w2.st; w3.en=w1.en>w2.en?w1.en:w2.en; w3.dur=w3.en-w3.st; // cout<<"new worker:"<<w3.st<<":"<<w3.en<<":"<<w3.dur<<endl; return w3; } void last_time() { int max_time=0; for(auto it:v) { max_time=max_time>it.dur?max_time:it.dur; } cout<<max_time<<" "; } void no_time() { sort(v.begin(),v.end(),[](const worker& x,const worker& y) { if(x.st==y.st) return x.en<y.en; else return x.st<y.st; }); int max_time=0; auto cur=v.begin(); auto last=cur; cur++; while(cur!=v.end()) { max_time=max_time>(cur->st-last->en)?max_time:(cur->st-last->en); last=cur; cur++; } cout<<max_time<<" "; } int main() { //提高cin,cout的速度 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // freopen("法师康的工人.in","r",stdin); // freopen("法师康的工人.ans","w",stdout); //begin code int n; cin>>n; worker temp_worker; while(n--) { cin>>temp_worker.st>>temp_worker.en; temp_worker.dur=temp_worker.en-temp_worker.st; for(auto iter=v.begin(); iter!=v.end();) { if(canMerge(temp_worker,*iter)) { temp_worker=merge(temp_worker,*iter); iter=v.erase(iter); } else { iter++; } } v.push_back(temp_worker); } last_time(); no_time(); // for(auto w:v){ // cout<<w.st<<":"<<w.en<<":"<<w.dur<<endl; // } //end code // fclose(stdin); // fclose(stdout); return 0; }
参考的方法,滑动窗口,一个不错的方法
#include<iostream> #include<algorithm> using namespace std; struct Worktime { int start; int end; Worktime(int s = NULL, int e = NULL) :start(s), end(e) {}; }; bool cmp(Worktime& a, Worktime& b) { if (a.start != b.start) return a.start < b.start; return a.end < b.end; } int main() { int N; cin >> N; Worktime* p = new Worktime[N]; for (int i = 0; i < N; i++) { int x; cin >> x; p[i].start = x; int y; cin >> y; p[i].end = y; } sort(p, p + N, cmp); int max1 = p[0].end - p[0].start; int max2 = 0; int start = p[0].start; int end = p[0].end; for (int i = 0; i <N-1; i+=1) { if (end >= p[i+1].start) { end = p[i + 1].end > end ? p[i + 1].end : end; max1 = end-start> max1 ? end-start : max1; } else { start = p[i + 1].start; max2 = p[i+1].start-end > max2 ? p[i+1].start - end : max2; end = p[i + 1].end; } } cout << max1 << ' ' << max2 << endl; return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。