Comet OJ - Contest #8 A.B.C
题目
A.杀手皇后
签到题，直接用string进行比较即可
/*
Algorithm:
Author: anthony1314
Creat Time:
Time Complexity:
*/
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
//#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;
int main() {
string maxx = "";
maxx += string(1001, '~');
int n;
cin>>n;
string q;
for(int i = 0; i < n; i++) {
cin>>q;
if(q < maxx){
maxx = q;
}
}
cout<<maxx<<endl;
return 0;
} B.支援城市
如果有n=3, 三个数为a, b, c,则对于c
/*
Algorithm:
Author: anthony1314
Creat Time:
Time Complexity:
*/
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
//#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;
ll a[100005];
ll b[100005];
int main() {
int n;
cin>>n;
ll sum1 = 0;
ll sum2 = 0;
for(int i = 0; i < n; i++){
scanf("%lld", &a[i]);
b[i] = a[i]*a[i];
sum1 += b[i];
sum2 += a[i];
}
for(int i = 0; i < n; i++){
if(i != 0) printf(" ");
printf("%lld", sum1+(n-2)*b[i]-2*a[i]*(sum2-a[i]));
}
puts("");
return 0;
} C.符文能量
n个符文石 会爆发n-1次能量，且不影响，先算出n-1能是多少
开两个数组记录 k倍符文能量爆发是多少 k^2倍符文能量爆发是多少
直接dp就行了 dp三个状态 还没区间 在选区间 已经选完区间 之间爆发的最少能量
/*
Algorithm:
Author: anthony1314
Creat Time:
Time Complexity:
*/
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
//#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;
ll a[100005];
ll b[100005];
ll num[100005];
ll dp[100005][5];
ll knum[100005];
ll k2num[100005];
int main() {
ll n, k;
cin>>n>>k;
for(int i = 0; i < n; i++){
scanf("%lld %lld", &a[i], &b[i]);
}
for(int i = 1; i < n; i++){
num[i] = a[i] * b[i-1];
knum[i] = k*num[i];
k2num[i] = k*k*num[i];
}
dp[1][0] = num[1];//没选
dp[1][1] = knum[1];//选完了
dp[1][2] = k2num[1];//还在选
for(int i = 2; i < n; i++){
dp[i][0] = dp[i-1][0] + num[i];
dp[i][1] = min(dp[i-1][1] + num[i], dp[i-1][2] + knum[i]);
dp[i][2] = min(dp[i-1][0] + knum[i], dp[i-1][2] + k2num[i]);
}
ll minn = min(min(dp[n-1][0], dp[n-1][1]), dp[n-1][2]);
cout<<minn<<endl;
return 0;
}
