ABC-325

D

题目链接
https://atcoder.jp/contests/abc325/tasks/abc325_d
题目大意

题目思路
贪心，每一次优先选取最先出去的，优先队列！
题目代码

#include<bits/stdc++.h> 
#define ll long long
using namespace std;
int n,ans;
int main()
{
	cin >> n;
	vector<array<ll,2>>a(n);
	for(auto& x:a) cin >> x[0] >> x[1];
	vector<int>id(n);
	iota(id.begin(),id.end(),0);
	sort(id.begin(),id.end(),[&](int x,int y){
		if(a[x][0] != a[y][0]) return a[x][0] < a[y][0];
		else                   return a[x][1] < a[y][1];
	});
	priority_queue<ll,vector<int>,greater<int>> q;
	ll time = 0;
	auto it = id.begin();
	while(!q.empty() || it != id.end())
	{
		if(q.empty()) time = a[*it][0];
		while(it != id.end() && a[*it][0] <= time){
			q.push(a[*it][0] + a[*it][1]);
			it = next(it);
		}
		while(!q.empty() && q.top() < time) q.pop();
		if(!q.empty() && q.top() >= time){
			++ans;++time;q.pop();
		}
	}
	cout << ans << '\n';
	return 0;
}

E

题目链接
https://atcoder.jp/contests/abc325/tasks/abc325_e
题目大意

题目思路
两次Dijkstra，一次从1开始，使用car,另一次从n开始，使用train
题目代码

#include<bits/stdc++.h>
#define ll long long
#define pi pair<ll,int>
const int inf = 1e18;
const int N = 1e3 + 5;
using namespace std;
int n,A,B,C,cost1,cost2;
int g[N][N];
ll dis1[N],dis2[N];
ll ans = inf;
void dijkstra1(int start){
	dis1[start] = 0;
	priority_queue<pi,vector<pi>,greater<pi>>q;
	q.push({0,start});
	while(!q.empty()){
		int d = q.top().first,u = q.top().second;q.pop();
		if(d > dis1[u]) continue;
		for(int v = 1;v <= n;++v){
			if(v == u) continue;
			if(dis1[v] > dis1[u] + g[u][v] * A){
				dis1[v] = dis1[u] + g[u][v] * A;
				q.push({dis1[v],v});
			}
		}
	}
}
void dijkstra2(int start){
	dis2[start] = 0;
	priority_queue<pi,vector<pi>,greater<pi>>q;
	q.push({0,start});
	while(!q.empty()){
		int d = q.top().first,u = q.top().second;q.pop();
		if(d > dis2[u]) continue;
		for(int v = 1;v <= n;++v){
			if(v == u) continue;
			if(dis2[v] > dis2[u] + g[u][v] * B + C){
				dis2[v] = dis2[u] + g[u][v] * B + C;
				q.push({dis2[v],v});
			}
		}
	}
}
int main()
{
	cin >> n >> A >> B >> C;
	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= n;++j)
			cin >> g[i][j];
	}
	for(int i = 1;i <= n;++i) dis1[i] = dis2[i] = inf;
	dijkstra1(1);dijkstra2(n);
	for(int i = 1;i <= n;++i){
		ans = min(ans,dis1[i] + dis2[i]);
	}
	cout << ans << '\n';
	return 0;
}

F

题目链接
https://atcoder.jp/contests/abc325/tasks/abc325_f
题目大意

题目思路
dp[i][j]表示从前i个物品中，执行操作1 j 次，执行了操作2 的最小操作次数！
题目代码

#include<bits/stdc++.h>
#define ll long long
const ll inf = 1e18;
const int N = 1e2 + 5;
using namespace std;
int n;
int D[N];
int L1,C1,K1,L2,C2,K2;
ll ans = inf;
int main()
{
	cin >> n;
	for(int i = 1;i <= n;++i) cin >> D[i];
	cin >> L1 >> C1 >> K1;
	cin >> L2 >> C2 >> K2;
	// dp[i][j]表示从前i个物品中，执行操作1 j 次，执行了操作2 的最小操作次数！ 
	vector<vector<ll>>dp(n + 1,vector<ll>(K1 + 1,inf));
	for(int i = 0;i <= K1;++i) dp[0][i] = 0;
	for(int i = 1;i <= n;++i){
		for(int j = 0;j <= K1;++j){
			for(int k = 0;k <= j;++k){
				//                            上取整！ 
				int v = max(0,(D[i] - k * L1 + L2 - 1) / L2);
				dp[i][j] = min(dp[i][j],dp[i - 1][j - k] + v);
			}
		}
	}
	for(int k1 = 0;k1 <= K1;++k1){
		if(dp[n][k1] <= K2){
			ans = min(ans,1ll * k1 * C1 + dp[n][k1] * C2);
		}	
	} 
	if(ans == inf) ans = -1;
	cout << ans << '\n';
	return 0;
}

G

题目链接
https://atcoder.jp/contests/abc325/tasks/abc325_g
题目大意

题目思路
dp[i][j] 表示 s[i..j] 经过操作后的最小长度！
题目代码

#include<bits/stdc++.h>
using namespace std;
string s;
int k;
int main()
{
	cin >> s >> k;
	// dp[i][j] 表示 s[i..j] 经过操作后的最小长度！ 
	vector<vector<int>>dp(s.size() + 1,vector<int>(s.size() + 1,0));
	for(int r = 0;r < s.size();++r){
		for(int l = r;l >= 0;--l){
			dp[l][r] = r - l + 1;
			for(int m = l;m < r;++m)
				dp[l][r] = min(dp[l][r],dp[l][m] + dp[m + 1][r]);
			if(s[l] == 'o'){
				for(int m = l + 1;m <= r;++m)
					if(s[m] == 'f' && dp[l + 1][m - 1] == 0)
						dp[l][r] = min(dp[l][r],max(0,dp[m + 1][r] - k));
			}
		}
	}
	cout << dp[0][s.size() - 1] << '\n';
	return 0;	
}