庆阳建设局网站,宁波建设信息网,网络推广外包费用,通过备案号查网站E - Greedy Ant
Grice题解最开始看不懂神的思路#xff0c;还评论请教了一波应该是个集训队大佬QaQ snuke在当前轮直接选取#xff0c;那么状态会非常不好记录 我们保留snuke在之前轮#xff0c;选择放弃暂时不选的次数#xff0c;然后等蚂蚁走到这来了再选 虽然这个跟原游…E - Greedy Ant
Grice题解最开始看不懂神的思路还评论请教了一波应该是个集训队大佬QaQ snuke在当前轮直接选取那么状态会非常不好记录 我们保留snuke在之前轮选择放弃暂时不选的次数然后等蚂蚁走到这来了再选 虽然这个跟原游戏不同但显然其不会优于最优解也包含最优解 状态表示fl,r,kf_{l,r,k}fl,r,k开区间(l,r)(l,r)(l,r)内的糖果已经被取走了snuke\text{snuke}snuke还能选择kkk次的最优解 状态转移
满足k0k0k0那么snuke\text{snuke}snuke可以选择lll或者rrr则分别转移到fl−1,r,k−1alf_{l-1,r,k-1}a_lfl−1,r,k−1al和fl,r1,k−1arf_{l,r1,k-1}a_rfl,r1,k−1ar目前snuke\text{snuke}snuke不选择则对手选择那么用fl−1,r,k1f_{l-1,r,k1}fl−1,r,k1或者fl,r1,k1f_{l,r1,k1}fl,r1,k1转移按照题意这里转移固定取al,ara_l,a_ral,ar较大的一个
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N410;
int n;
ll f[N][N][N],a[N];
ll dp(int l,int r,int k)
{if(f[l][r][k]!-1) return f[l][r][k];ll ansf[l][r][k];ans0;if(l1){if(k) ansmax(ans,a[l]dp(l-1,r,k-1));if(a[l]a[r]) ansmax(ans,dp(l-1,r,k1));}if(rn){if(k) ansmax(ans,a[r]dp(l,r1,k-1));if(a[r]a[l]) ansmax(ans,dp(l,r1,k1));}return ans;}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinn;for(int i1;in;i) cina[i];memset(f,-1,sizeof f);for(int i0;in;i)coutdp(i,i1,1)\n;return 0;
}上述博客博主太热心了并且讲的非常详细以至于题解总结基本都是抄的~~
