Codeforces 940 区间DP单调队列优化

#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-8;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int maxm = ;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
ll mod = 3e7;
int num[];
int main()
{
int n, d;
cin >> n >> d;
int anser = ;
for (int i = ; i <= n; i++)
{
cin >> num[i];
}
if (n == )
{
cout << << endl;
return ;
}
sort(num + , num + + n);
int now = num[n] - num[];
int l = ;
int r = n;
for (int i = n - ; i >= ; i--)
{
for (int j = ; j <= n - i; j++)
{
if (num[j + i] - num[j] <= d)
{
cout << n - i - << endl;
return ;
}
}
}
cout<<n-<<endl;
return ;
}

#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-8;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int maxm = ;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
ll mod = 3e7;
int num[];
int main()
{
ll n, k, a, b;
cin >> n >> k >> a >> b;
ll now = n;
ll cost = ;
ll remain, aim;
if (k == )
{
cost += 1LL * a * (now - );
cout << cost << endl;
return ;
}
while (now != )
{
if (now < k)
{
cost += 1LL * a * (now - );
break;
}
remain = now % k;
cost += remain * a;
now -= remain;
aim = now / k;
cost += min(1LL * a * (now - aim), 1LL * b);
now = aim;
}
cout << cost << endl;
return ;
}

#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-8;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int maxm = ;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
ll mod = 3e7;
int num[];
int nextt[];
int main()
{
int n, k;
string a;
cin >> n >> k >> a;
for (int i = ; i < n; i++)
{
num[a[i] - 'a'] = ;
}
for (int i = ; i <= ; i++)
{
for (int j = i + ; j <= ; j++)
{
if (num[j])
{
nextt[i] = j;
break;
}
}
}
if (k > n)
{
cout << a;
int aim;
for (int i = ; i <= ; i++)
{
if (num[i])
{
aim = i;
break;
}
}
char ch = 'a' + aim;
for (int i = ; i <= k - n; i++)
{
cout << ch;
}
cout << endl;
}
else
{
int aim;
int cur;
for (int i = k - ; i >= ; i--)
{
if (nextt[a[i] - 'a'] != )
{
aim = nextt[a[i] - 'a'];
cur = i;
break;
}
}
for (int i = ; i < cur; i++)
{
cout << a[i];
}
char ch = aim + 'a';
cout << ch;
for (int i = ; i <= ; i++)
{
if (num[i])
{
aim = i;
break;
}
}
ch = aim + 'a';
for (int i = ; i <= k - cur - ; i++)
{
cout << ch;
}
cout << endl;
}
return ;
}

#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-8;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int maxm = ;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
ll mod = 3e7;
int num[];
int minnum[];
int maxnum[];
int main()
{
int n;
cin >> n;
for (int i = ; i <= n; i++)
{
scanf("%d", &num[i]);
}
string a;
cin >> a;
for (int i = ; i <= n; i++)
{
int maxn = -;
for (int j = ; j <= ; j++)
{
maxn = max(maxn, num[i - j]);
}
maxnum[i] = maxn;
}
for (int i = ; i <= n; i++)
{
int minn = ;
for (int j = ; j <= ; j++)
{
minn = min(minn, num[i - j]);
}
minnum[i] = minn;
}
int l = -;
int r = ;
for (int i = ; i <= n - ; i++)
{
if (a[i] == '' && a[i - ] == '')
{
l = max(l, maxnum[i + ] + );
}
if (a[i] == '' && a[i - ] == '')
{
r = min(r, minnum[i + ] - );
}
}
cout << l << " " << r << endl;
return ;
}

#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
const double EPS = 1.0e-4;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
const int MAXN = 1e5 + ;
ll num[MAXN];
int q[MAXN];
int head, tail;
ll dp[MAXN];
ll pre[MAXN];
list<int> que;
int main()
{
int n, c;
cin >> n >> c;
for (int i = ; i <= n; i++)
{
scanf("%lld", num + i);
pre[i] = pre[i - ] + num[i];
}
for (int i = ; i <= n; i++)
{
dp[i] = dp[i - ] + num[i];
while (head >= tail && i - c >= q[tail])
{
tail++;
}
while (head >= tail && num[q[head]] > num[i])
{
head--;
}
q[++head] = i;
if (i >= c)
{
dp[i] = min(dp[i], dp[i - c] + pre[i] - pre[i - c] - num[q[tail]]);
}
}
cout << dp[n] << endl;
}