洛谷P2196 挖地雷(dp)

## 题意 [题目链接](https://www.luogu.org/problemnew/show/p2196) ## sol 早年noip的题锅好多啊。。 这题连有向边还是无向边都没说(~~害的我wa了一遍~~) 直接$f[i]$表示到第$i$个点的贡献 转移的时候枚举从哪个点转移而来 然后我就用一个$n^2$的算法过了一道$n \leqslant 20$的题？？。。 ```cpp #include #include #include using namespace std; const int maxn = 101; inline int read() { char c = getchar(); int x = 0, f = 1; while(c '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c =>=>=>=>=> f[i]) f[i] = f[j], pre[i] = j; f[i] += a[i]; if(f[i] > ans) ans = f[i], ed = i; } vector v; while(ed) v.push_back(ed), ed = pre[ed]; for(int i = v.size() - 1; i >= 0; i--) printf("%d ", v[i]); puts(""); printf("%d", ans); return 0; } ```=>