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;
}