記錄第一次CCSP競賽。一共3題，只做出第一題，用時3h30m（累），ac了開心地吃了個午飯。然而飯飽之后，大腦完全提不起神看著題面昏昏欲睡。第二題是虛擬內(nèi)存，超級大模擬，剛好這個學(xué)期學(xué)os，但是翹了太多課完全看不懂，自己看ppt學(xué)了一點多級頁表，但是1v0，1v1啥的想不明白怎么對應(yīng)呀。第三題跟數(shù)據(jù)庫系統(tǒng)有關(guān)，高性能 RDF 圖查詢系統(tǒng)，給了一個代碼框架，稍微看了看，代碼十分規(guī)范，應(yīng)用了很多C++繼承、虛基類等等特性，然后按要求實現(xiàn)一些函數(shù)方法，不會。下面主要記錄第一題的思路。
T1 最少充電次數(shù)
題面
數(shù)據(jù)范圍：
思路
DP，有電量、充電時間兩個維度約束，一開始我定義的狀態(tài)是 d p [ n ] [ r t i m e ] [ r b a t ] dp[n][rtime][rbat] dp[n][rtime][rbat]，維度的含義是當(dāng)前站點、剩余充電時間和剩余電量，存儲相應(yīng)的最小充電次數(shù)，但是更新該狀態(tài)數(shù)組會發(fā)現(xiàn)剩余電量這一維度是 ( 1 < < 30 ) ≈ 1 e 9 (1<<30)\approx1e9 (1<<30)≈1e9，這肯定T飛。
其實看到問題很容易產(chǎn)生貪心想法，選擇充電效率較高的充電站以在相同的時間內(nèi)獲得更多電量。那其他維度相同的狀態(tài)中是不是應(yīng)選擇剩余電量更多的狀態(tài)？想到這點，重新定義狀態(tài)
d
p
[
n
]
[
r
t
i
m
e
]
[
a
n
s
]
dp[n][rtime][ans]
dp[n][rtime][ans]，調(diào)換一下，最后一維表示充電次數(shù)，數(shù)組存儲最大剩余電量。
遞推分為行駛和充電，由于當(dāng)前狀態(tài)僅僅和前面一個狀態(tài)有關(guān)，將第一維度賦為2，滾動數(shù)組以壓縮空間。
① 行駛至下一個充電站：
dp[s ^ 1][j][k] = max(dp[s ^ 1][j][k], dp[s][j][k] - d[i + 1] + d[i]);
② 充電：
dp[s ^ 1][j][k] = dp[s][j][k]; // t==0
dp[s ^ 1][j - t][k + 1] = max(dp[s ^ 1][j - t][k + 1], dp[s][j][k] + t * cspeed[i]); // t!=0
優(yōu)化
仔細(xì)算一下復(fù)雜度，充電站數(shù)×總最大充電時間×充電次數(shù)，
512
×
1
e
4
×
512
≈
2.5
e
9
512\times1e4\times512\approx2.5e9
512×1e4×512≈2.5e9，提交上去只能過前面兩個點。
然后，開始想辦法借助STL進(jìn)行優(yōu)化（感覺CCF比賽我總是靠亂搞STL出奇跡）。
用數(shù)組存儲狀態(tài)，你只能按下標(biāo)進(jìn)行遞推，但這會冗余考慮很多不可能的狀態(tài)，從不可能的狀態(tài)遞推怎么也無法到達(dá)可能的狀態(tài)。于是乎我改用
m
a
p
<
n
o
d
e
,
i
n
t
>
s
t
a
t
[
2
]
map<node, int> stat[2]
map<node,int>stat[2]，其中 node 的定義為
struct node {
int rtime, cnt;
bool operator < (const node &d) const {
return cnt < d.cnt;
}
};
這個結(jié)構(gòu)僅僅存儲有效狀態(tài)，因而我們也只會從有效狀態(tài)開始遞推，避免冗余。
AC代碼
太菜了，一發(fā)AC高興得不得來了。。。文章來源：http://www.zghlxwxcb.cn/news/detail-717552.html
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int d[550], tlimit[550], cspeed[550];
struct node {
int rtime, cnt;
bool operator < (const node &d) const {
return cnt < d.cnt;
}
};
// 只對有效狀態(tài)進(jìn)行轉(zhuǎn)移
map<node, int> stat[2];
void solve() {
int totdis, n, maxtime, initbat;
cin >> totdis >> n >> maxtime >> initbat;
d[0] = 0;
for (int i = 1; i <= n; i++) cin >> d[i];
for (int i = 0; i < n; i++) cin >> tlimit[i];
for (int i = 0; i < n; i++) cin >> cspeed[i];
stat[1][{maxtime, 0}] = initbat;
int s = 1;
for (int i = 0; i < n; i++) {
// 從i-1行駛至i
for (const auto &[x, r] : stat[s]) {
if (stat[s][x] - d[i + 1] + d[i] >= 0) {
stat[s ^ 1][x] = stat[s][x] - d[i + 1] + d[i];
}
}
stat[s].clear();
s ^= 1;
// 充電
for (int t = 0; t <= tlimit[i]; t++) {
// 狀態(tài)轉(zhuǎn)移
for (const auto &[x, r] : stat[s]) {
if (x.rtime < t) continue;
if (t) {
int tmp = 0;
if (stat[s ^ 1][{x.rtime - t, x.cnt + 1}]) {
tmp = stat[s ^ 1][{x.rtime - t, x.cnt + 1}];
}
stat[s ^ 1][{x.rtime - t, x.cnt + 1}] = max(tmp, r + t * cspeed[i]);
}
else { stat[s ^ 1][{x.rtime, x.cnt}] = r; }
}
}
stat[s].clear();
s ^= 1;
}
// ans
for (const auto &[x, r] : stat[s]) {
if (r >= totdis - d[n]) {
cout << x.cnt << '\n';
return;
}
}
{ cout << "-1\n"; }
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}
提交代碼
僅僅作為個人記錄。文章來源地址http://www.zghlxwxcb.cn/news/detail-717552.html
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define Debug
//#define arr
// 選擇充電不一定會充至?xí)r間上限
// dp[n][rtime][rbat]:充電次數(shù)，（當(dāng)前所在充電站、剩余充電時間、剩余電量）
// 512*(1e4)*(1<<30)
// 到達(dá)終點最少充電次數(shù)
/*
* dp[i][rtime][rbat]=dp[i-1][rtime][rbat+d[i]-d[i-1]]
* dp[i][rtime-t][rbat+t*cspeed[i]]=dp[i][rtime][rbat]+1,t<=tlimit[i]
*/
// 分組背包
// 每組取物品個數(shù)=每個服務(wù)站充電時間
// 充電速度不同->選擇剩余電量最多的狀態(tài)
// dp[n][rtime][ans]
/*
* dp[n][rtime][i]=max(dp[n][rtime+t][i-1]+t*cspeed[i])
*/
int d[550], tlimit[550], cspeed[550];
#ifdef arr
int dp[2][10010][550]; // 該狀態(tài)下最大剩余電量
#else
struct node {
int rtime, cnt;
bool operator < (const node &d) const {
return cnt < d.cnt;
}
};
// 只對有效狀態(tài)進(jìn)行轉(zhuǎn)移
map<node, int> stat[2];
#endif
void solve() {
int totdis, n, maxtime, initbat;
cin >> totdis >> n >> maxtime >> initbat;
d[0] = 0;
for (int i = 1; i <= n; i++) cin >> d[i];
for (int i = 0; i < n; i++) cin >> tlimit[i];
for (int i = 0; i < n; i++) cin >> cspeed[i];
#ifdef arr
memset(dp, -1, sizeof dp);
dp[1][maxtime][0] = initbat; // 初始化
#else
stat[1][{maxtime, 0}] = initbat;
#endif
int s = 1;
for (int i = 0; i < n; i++) {
// 從i-1行駛至i
#ifdef arr
for (int j = maxtime; j >= 0; j--) {
for (int k = 0; k <= i; k++) {
dp[s ^ 1][j][k] = max(dp[s ^ 1][j][k], dp[s][j][k] - d[i + 1] + d[i]);
}
}
#else
for (const auto &[x, r] : stat[s]) {
if (stat[s][x] - d[i + 1] + d[i] >= 0) {
stat[s ^ 1][x] = stat[s][x] - d[i + 1] + d[i];
}
}
#endif
#ifdef Debug
cout << "arrive: " << i << '\n';
// for (int j = maxtime; j >= 0; j--) {
// cout << "rest time: " << j << '\n';
// for (int k = 0; k <= i && k <= n; k++) {
// cout << "(" << k << "," << dp[s ^ 1][j][k] << ") ";
// }
// cout << '\n';
// } cout << '\n';
for (const auto &x : stat[s ^ 1]) {
cout << x.rtime << ' ' << x.cnt << ' ' << x.rbat << '\n';
} cout << '\n';
#endif
#ifdef arr
memset(dp[s], -1, sizeof dp[s]);
#else
stat[s].clear();
#endif
s ^= 1;
// 充電
for (int t = 0; t <= tlimit[i]; t++) {
// 狀態(tài)轉(zhuǎn)移
#ifdef arr
for (int j = maxtime; j >= 0; j--) {
if (j < t) break;
for (int k = 0; k <= i && k <= n; k++) {
if (!t) {
dp[s ^ 1][j][k] = dp[s][j][k];
}
else {
if (dp[s][j][k] < 0) continue;
dp[s ^ 1][j - t][k + 1] = max(dp[s ^ 1][j - t][k + 1], dp[s][j][k] + t * cspeed[i]);
}
}
}
#else
for (const auto &[x, r] : stat[s]) {
if (x.rtime < t) continue;
if (t) {
int tmp = 0;
if (stat[s ^ 1][{x.rtime - t, x.cnt + 1}]) {
tmp = stat[s ^ 1][{x.rtime - t, x.cnt + 1}];
}
stat[s ^ 1][{x.rtime - t, x.cnt + 1}] = max(tmp, r + t * cspeed[i]);
}
else { stat[s ^ 1][{x.rtime, x.cnt}] = r; }
}
#endif
}
#ifdef Debug
cout << "charge: " << i << '\n';
// for (int j = maxtime; j >= 0; j--) {
// cout << "rest time: " << j << '\n';
// for (int k = 0; k <= (i + 1) && k <= n; k++) {
// cout << "(" << k << "," << dp[s ^ 1][j][k] << ") ";
// }
// cout << '\n';
// } cout << '\n';
for (const auto &x : stat[s ^ 1]) {
cout << x.rtime << ' ' << x.cnt << ' ' << x.rbat << '\n';
} cout << '\n';
#endif
// memset(dp[s], -1, sizeof dp[s]);
#ifdef arr
memset(dp[s], -1, sizeof dp[s]);
#else
stat[s].clear();
#endif
s ^= 1;
}
// ans
#ifdef arr
for (int k = 0; k <= n; k++) {
for (int j = maxtime; j >= 0; j--) {
if (dp[s][j][k] >= totdis - d[n]) {
cout << k << '\n';
return;
}
}
}
#else
for (const auto &[x, r] : stat[s]) {
if (r >= totdis - d[n]) {
cout << x.cnt << '\n';
return;
}
}
#endif
{ cout << "-1\n"; }
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}
/*
10 2 2 2
3 8
1 1
2 3
10 2 2 5
3 8
1 1
3 2
*/
到了這里，關(guān)于2022CCSP T1最少充電次數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
