AKSZ-动态规划
2024-06-16 17:32:42
发布于:广东
动态规划
1.划分阶段 斐波那契数列每一项数列作为一个阶段
2.确定状态 第项的值用数组第位确定:
3.确定状态并写出状态转移方程式
#include<bits/stdc++.h>
using namespace std;
int main(){
//结尾法
//dp[i]表示以下标i结尾的答案
int dp[2000005],n,a[2000005];
cin>>n;
for(int i = 1;i<=n;i++){
cin>>a[i];
}
//边界问题
dp[1] = a[1];
for(int i = 1;i<=n;i++){
if(dp[i-1]<0) dp[i] = a[i];
if(dp[i-1]>=0) dp[i] = dp[i-1]+a[i];
}
//数据问题
int maxx = a[1];
for(int i = 1;i<=n;i++){
maxx = max(maxx,dp[i]);
}
cout<<maxx;
//max{dp[i]~dp[n]};
return 0;
}
全部评论 2
我嘞个豆开这么大数组
2024-06-19 来自 广东
0数组不要定义在main里面
2024-06-19 来自 广东
0
有帮助,赞一个