ATcoder abc 453C题 状态压缩枚举，暂时没找到别的写法

题目链接

https://atcoder.jp/contests/abc453/tasks/abc453_c

code

#include<iostream>
#include<cassert>
using namespace std;
#define int long long
int N,L[20];
//直接枚举所有的部分
//从0~2^5，中间出现了所有可能出现的0一排列，1代表往正方向走，0代表往负方向走，把所有的组合都试一次
//这样就可以得到最大的cnt
//好像只能状态压缩枚举了
signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin>>N;for(int i=0;i<N;i++)cin>>L[i];int ans=0;for(int i=0;i<1<<N;i++){int cur=0;int cnt=0;for(int j=0;j<N;j++){int nxt=cur;if(i>>j&1)nxt+=L[j];else nxt-=L[j];if(cur>=0&&nxt<0||cur<0&&nxt>=0)cnt++;cur=nxt;}ans=max(ans,cnt);}cout<<ans<<endl;
}

分析

直接枚举所有的部分
从0~2^5，中间出现了所有可能出现的01排列，1代表往正方向走，0代表往负方向走，把所有的组合都试一次
这样就可以得到最大的cnt
好像只能状态压缩枚举了