E题为什么开滚动数组是就不对
#include<bits/stdc++.h> using namespace std; #define int long long #define debug(x) cout << #x << " " << x << endl; signed main() { int n,K; cin >> n >> K; vector<int> a(n + 1); for(int i = 1;i <= n;i ++){ cin >> a[i]; } vector<vector<int>> dp(2,vector<int>(n + 1,-1e18)); dp[0][0] = 0; dp[1][0] = 0; int ans = -1e18; for(int k = 1;k <= K;k ++){ //cout << "____________________________________" << endl; //debug(k); for(int i = k;i <= k * 6;i ++){ for(int j = 1;j <= min(6LL,i);j ++){ dp[k & 1][i] = max(dp[k & 1][i],dp[k - 1 & 1][i - j] + a[i]); } //debug(dp[k & 1][i]); } } for(int i = 1;i <= n;i ++){ ans = max(ans,dp[K & 1][i]); } cout << ans << endl; }
但是不用滚动数组就对了
#include<bits/stdc++.h> using namespace std; #define int long long #define debug(x) cout << #x << " " << x << endl; signed main() { int n,K; cin >> n >> K; vector<int> a(n + 1); for(int i = 1;i <= n;i ++){ cin >> a[i]; } vector<vector<int>> dp(K + 1,vector<int>(n + 1,-1e18)); dp[0][0] = 0; int ans = -1e18; for(int k = 1;k <= K;k ++){ //cout << "____________________________________" << endl; //debug(k); for(int i = k;i <= k * 6;i ++){ for(int j = 1;j <= min(6LL,i);j ++){ dp[k][i] = max(dp[k][i],dp[k - 1][i - j] + a[i]); } //debug(dp[k & 1][i]); } } for(int i = 1;i <= n;i ++){ ans = max(ans,dp[K][i]); } cout << ans << endl; }
求助