#include<iostream> using namespace std; int n,m,k,T; int a[10001],dp[10001]; int main(){ cin>>T; while(T--){ while(cin>>n>>m>>k){ for(int i=1;i<=n;i++) { dp[i]=99999; a[i]=0;} for(int i=1;i<=m;i++) { int j; cin>>j; a[j]=1; }// if(a[1]==1) dp[1]=1; else dp[1]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=k;j++) { if(i+j>n) break; if(dp[i]+a[i+j]<dp[i+j]) dp[i+j]=dp[i]+a[i+j]; } } //for(int i=1;i<=n;i++) //cout<<dp[i]<<" "; //cout<<endl; cout<<dp[n]<<endl;} } return 0; }
时间: 2024-03-19 08:42:14 浏览: 20
这段代码的实现思路和我之前给出的动态规划算法是一致的,使用 dp[i] 表示到达位置 i 时最少踩水坑的次数,状态转移方程为:
dp[i] = min(dp[i-j] + a[i]),其中 j 的取值范围为 [1, k],且位置 i-j 到位置 i 之间没有积水。
其中,a[i] 表示位置 i 是否有积水,有积水的话需要额外增加一次踩水坑的次数。
初始状态为 dp[1] = 0。
这段代码的时间复杂度为 O(T * n * k),其中 T 表示测试用例的个数。空间复杂度为 O(n)。
需要注意的是,在输入时需要将 T 放在最外层循环,而不是内层循环。同时,输入时需要对 a 数组进行初始化,因为可能存在多组测试用例,如果不初始化的话,上一组测试用例中的积水位置可能会影响下一组测试用例的结果。另外,判断是否越界应该在 j 的循环内部进行,而不是在外层循环中判断。
以下是经过修改后的代码实现:
相关问题
#include <iostream>#include <cstring>using namespace std;const int N = 1e6 + 10, MOD = 1e9 + 7;int n;int dp[N];int main(){ cin >> n; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i ++) dp[i] = (dp[i - 1] + dp[i - 2]) % MOD; cout << dp[n] << endl; return 0;}请将这段代码时间复杂度降低并展示给我
这段代码已经是 $O(n)$ 的时间复杂度,不过可以使用滚动数组进一步优化空间复杂度,将空间复杂度降为 $O(1)$。如下所示:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 1e9 + 7;
int n;
int a = 1, b = 1, c;
int main() {
cin >> n;
if (n == 0) cout << 1 << endl;
else if (n == 1) cout << 1 << endl;
else {
for (int i = 2; i <= n; i++) {
c = (a + b) % MOD;
a = b;
b = c;
}
cout << b << endl;
}
return 0;
}
```
在这个版本中,我们只使用了三个变量 a、b 和 c,避免了使用数组来存储所有的 dp 值,从而将空间复杂度降低为 $O(1)$。
优化这条代码#include <iostream> #include <vector> using namespace std; int longestIncreasingSubsequence(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 1); int maxLen = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = max(dp[i], dp[j] + 1); } } maxLen = max(maxLen, dp[i]); } return maxLen; } int main() { int n; cin >> n; vector<int> nums(n); for (int i = 0; i < n; i++) { cin >> nums[i]; } int result = longestIncreasingSubsequence(nums); cout << result << endl; return 0; }
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int longestIncreasingSubsequence(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
int result = longestIncreasingSubsequence(nums);
cout << result << endl;
return 0;
}