欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷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; } ```=>