关于环上最大独立集
  • 板块学术版
  • 楼主timmark
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/8/14 09:22
  • 上次更新2023/11/3 03:58:20
查看原帖
关于环上最大独立集
566935
timmark楼主2023/8/14 09:22

rt,为什么这种作法会出错。

#include<bits/stdc++.h>
using namespace std;
long long n,a[100005],f[2][100005]; 
int main(){
	cin >> n ;
	for(int i=1;i<=n;i++) cin >> a[i] ;
	f[0][1]=a[1];//先拿上第一个
	for(int i=3;i<n;i++) f[0][i]=max(f[0][i-2]+a[i],f[0][i-1]);//第一个强制拿
	for(int i=2;i<=n;i++) f[1][i]=max(f[1][i-2]+a[i],f[1][i-1]);//第一个强制不拿
	cout << max(f[0][n-1],f[1][n]) ;
	return 0;
}
2023/8/14 09:22
加载中...