dp,01背包问题
但这里的f(i,j):i表示从1~i中选,j表示0,1,即第i个选还是不选
C++ 代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
int n;
int dp[N][3];
int a[N];
//01背包问题
//dp
//这里的f(i,j):i表示从1~i中选,j表示0,1,即第i个选还是不选
int main(){
int t;
cin>>t;
while(t--){
cin>>n;
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++)cin>>a[i];
dp[1][0]=0;
dp[1][1]=a[1];
for(int i=2;i<=n;i++){
dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
dp[i][1]=dp[i-1][0]+a[i];
}
cout<<max(dp[n][0],dp[n][1])<<endl;
}
return 0;
}