f[x] 表示走到第x枚金币时可以取到的最大的价值，sum表示剩下的总价值
因为金币的总价值是不变的，所以想要自己拿到最大的价值，就需要让女仆拿到最小的价值
转移方程：
f[x]=sum-min{f[x+1],f[x+2],f[x+3]}
终止条件：
剩下的金币数量<=3，全部拿走为最佳方案
#include <iostream> #include <cstring> #include <cmath> using namespace std; #define MAX 100005 long long f[MAX]; long long w[MAX]; int t,n; long long dfs(int x,long long sum) { if (f[x]>=0) return f[x]; if(x==n){ f[x]=w[x]; return f[x]; }else if(x==n-1){ f[x]=w[x]+w[x+1]; return f[x]; }else if(x==n-2){ f[x]=w[x]+w[x+1]+w[x+2]; return f[x]; } long long mi=min(dfs(x+1,sum-w[x]),dfs(x+2,sum-w[x]-w[x+1])); mi=min(mi,dfs(x+3,sum-w[x]-w[x+1]-w[x+2])); f[x]=sum-mi; return f[x]; } int main() { cin>>t; long long sum; while (t--) { cin>>n; sum=0; memset(f,-1,sizeof(f)); for (int i=1;i<=n;i++) { cin>>w[i]; sum+=w[i]; } cout<<dfs(1,sum)<<endl; } return 0; }