3067: 大盗阿福 DP

解题思路:f[i]表示前i店铺能获取的最大值， j表示不相邻的前j个店铺

注意事项:内层循环倒序， 注意递推的顺序

参考代码:

#include<iostream>
#include<cstring>
#include<algorithm> 
using namespace std;
const int N = 1e5 + 10;
int a[N],f[N],t,n;
int main()
{
	cin >> t;
	while(t --){
		memset(a, 0, sizeof a);
		memset(f, 0, sizeof f);
		cin >> n;
		for(int i = 1; i <=n; i ++ ) cin >> a[i];
		f[1] = a[1];
		for(int i = 2; i <= n; i ++)
			for(int j = i - 1; j >=1 ; j --)
				f[i] = max(f[i-1],f[i-j-1] + a[i]);
		cout << f[n] << endl;
	}

	return 0;
}

第二种解法：

#include<iostream>
#include<cstring>
#include<algorithm> 
using namespace std;
const int N = 1e5 + 10;
int a[N],f[N][2],t,n;
int main()
{
	cin >> t;
	while(t --){
		memset(a, 0, sizeof a);
		memset(f, 0, sizeof f);
		cin >> n;
		for(int i = 1; i <=n; i ++ ) cin >> a[i];
		for(int i = 1; i <= n; i ++){
			f[i][0] = max(f[i-1][0], f[i-1][1]);
			f[i][1] = f[i-1][0] + a[i];
		}
		cout << max(f[n][0],f[n][1]) << endl;
	}
	return 0;
}