上图为dpfun函数的send2的解析
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int k, a;
vector<vector<int>> cap(41, vector<int>(2));//节点能力数组,发送能力,存储能力
int res;
vector<int> dpfun(vector<int> pre, vector<int> cap) {
int send1 = min(pre[0], cap[0]);//第一次发送的数据包量
int send2 = min(cap[0], pre[1] + cap[1]);//第二次发送的数据包量
if (pre[0] - cap[0] > 0) send2 = min(pre[0] - cap[0] + pre[1], send2);//如果缓存没存满,并且缓存大于0
else send2 = min(send2, pre[1]); //缓存=0;
vector<int> r = { send1,send2 };
return r;
}
int main() {
cin >> k;
vector<vector<int>> dp(k+1, vector<int>(2));//代表第i个节点发送的数据包数
char c;
for (int i = 1; i <= k; i++) {
cin >> cap[i][0] >> c >> cap[i][1];
}
cin >> a;
dp[0][0] = a;//第0个节点第一次发送a
dp[0][1] = 0;//第二次发送0;
dp[1] = dpfun(dp[0], cap[1]);
res = min(dp[0][0] + dp[0][1], dp[1][0] + dp[1][1]);//如果只有一个节点,那么选择是故障还是不故障多
if (k == 0) {
cout << a;
}
else {
for (int i = 2; i <= k; i++) {
vector<int> res1 = dpfun(dp[i - 1], cap[i]);//前一个点没有故障
vector<int> res2 = dpfun(dp[i - 2], cap[i]);//前一个点故障
dp[i] = res1[0] + res1[1] <= res2[0] + res2[1] ? res1 : res2;//选择值最小的方案
}
res = min(dp[k][0] + dp[k][1], dp[k - 1][0] + dp[k - 1][1]);
}
cout << res;
return 0;
}
全部评论
(3) 回帖