洛谷P2196 挖地雷(dp)
程序员文章站
2022-03-30 20:12:39
题意 "题目链接" Sol 早年NOIP的题锅好多啊。。 这题连有向边还是无向边都没说(~~害的我wa了一遍~~) 直接$f[i]$表示到第$i$个点的贡献 转移的时候枚举从哪个点转移而来 然后我就用一个$n^2$的算法过了一道$n \leqslant 20$的题??。。 ......
## 题意
[题目链接](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;
}
``` =>
下一篇: 聊聊Java Double相加出现的怪事