5711 取数-1
状态表示:1维
集合:前 \(i\) 个数里面选法和的最大值
属性:Max
状态计算:选或不选
选:\(f(i-1)+a_i\) 不选:\(f(i-1)\)
#include <iostream>
using namespace std;
const int N = 55;
int a[N],f[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
f[1]=a[1];
for(int i=2;i<=n;i++)
f[i]=max(f[i-2]+a[i],f[i-1]);
cout<<f[n];
return 0;
}
5712 取数-2
状态表示:1维
集合:前 \(i\) 个数所有选法和的最大值
属性:Max
状态计算:连续选2个或不选
连续选两个:\(f(i-3)+a_{i-1}+a_i\) (注意要隔一个,不然就连起来了) 不选:\(f(i-1)\)
记得开 long long,因为 \(10^5×10^5\) 爆掉了(估算,实际上没有这么多,但是超过int的取值范围了)
#include <iostream>
using namespace std;
const int N = 1000010;
typedef long long LL;
int a[N];
LL f[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
f[2]=a[1]+a[2];
for(int i=3;i<=n;i++)
f[i]=max(f[i-1],f[i-3]+a[i-1]+a[i]);
cout<<f[n];
return 0;
}
5713 取数-3
状态表示:1维
集合:前 \(i\) 个数所有选法和的最大值
属性:Max
状态计算:不选,选1个,连续选2个
不选:\(f(i-1)\) 选1个:\(f(i-1)+a_i\) 选2个:\(f(i-3)+a_{i-1}+a_i\) (注意隔一个)
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 10005;
LL f[N];
LL a[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
f[1]=a[1];
for(int i=2;i<=n;i++)
f[i]=max(f[i-1],max(f[i-3]+a[i-1]+a[i],f[i-2]+a[i]));
cout<<f[n];
return 0;
}
标签:const,nflsoj,选法,int,选数,LL,不选,long
From: https://www.cnblogs.com/xiaozhu0602/p/17610115.html