显然是暴力模拟。。好难写 vector+map判重即可，其实也不难写，考试的时候没想到。。
#include #include #include #include #include #define rep(i,j,k) for(register int i(j);i<=k;++i) #define drp(i,j,k) for(register int i(j);i>=k;--i) #define bug cout<<"~~~~~~~~~~~~~"<<'\n'; #define bugout(x) cout< inline T max(T a, T b) { return a > b ? a : b; } template inline T min(T &a, T &b) { return a < b ? a : b; } template inline void swap(T &a, T &b) { T c; c = a; a = b; b = c; } using std::cin; using std::ios; using std::cout; const int N = 17; int n, m, x, L, ok; std::map< std::vector, bool> mp; std::vector a, goal; inline std::vector fold(int pos, std::vector &v) { std::vectoru; u.push_back(0); int l = v.size() - 1; int t = max(pos, l - pos); drp(i, t, 1) { int z = 0; if(pos - i + 1 > 0) z += v[pos - i + 1]; if(pos + i <= l) z += v[pos + i]; u.push_back(z); } return u; } inline bool equal(const std::vector &v) { rep(i, 1, m) { if(v[i] != goal[i]) return false; } return true; } inline void dfs(std::vector v) { if(ok) return ; if(mp.find(v) != mp.end()) return ; mp[v] = 1; int l = v.size() - 1; if(l == L) { if(equal(v)) ok = 1; } rep(i, 0, l) { dfs(fold(i, v)); } } int main() { freopen("fold.in", "r", stdin); freopen("fold.out", "w", stdout); ios::sync_with_stdio(false); while(cin >> n) { a.clear(); goal.clear(); a.push_back(0); goal.push_back(0); mp.clear(); rep(i, 1, n) { cin >> x; a.push_back(x); } cin >> m; rep(i, 1, m) { cin >> x; goal.push_back(x); } L = goal.size() - 1; ok = 0; dfs(a); puts(ok ? "S" : "N"); } return 0; }