Views

#include #include #include using namespace std; #define pow2(x) (1«(x)) const int maxn = 103; const int maxm = 19; const int maxs = pow2(16) + 3; int n, m, e, d[maxn], c[maxn][maxm], f[maxs], g[maxs]; inline void upMin(int& a, const int& b) { if (a > b) a = b; } int main() { #ifdef LAEKOV_LOCAL freopen(".in", “r”, stdin); #endif scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++ i) { scanf("%d", d + i); for (int j = 0; j < m; ++ j) scanf("%d", c[i] + j); } memset(f, 0x3f, sizeof(f)); f[0] = 0; e = pow2(m); for (int i = 1; i <= n; ++ i) { memset(g, 0x3f, sizeof(int) * e); for (int j = 0; j < m; ++ j) for (int k = e - 1; k >= 0; -- k) if (k & pow2(j)) { upMin(g[k], g[k ^ pow2(j)] + c[i][j]); upMin(g[k], f[k ^ pow2(j)] + d[i] + c[i][j]); } for (int j = 0; j < e; ++ j) upMin(g[j], f[j]); memcpy(f, g, sizeof(int) * e); } printf("%d\n", f[e - 1]); }

最近总是被一些水题虐智商啊…怎么回事Ovo 无脑地状压dp一下就好了. 每个物品分开dp,这样可以降到O(2m * n * m)级别. 我还是太弱了.

naive之laekov系列.这么水的题还想了几天ovoovo 这个距离,咦,不是传统的距离啊.等距线是十字形的. 思考一下.发现,分别按x和y排序,把相邻的两点之间连边,dijkstra,完了. 为啥啊?因为这样建图可以保证任意两点的最短路一定能在图上跑出来. 毕竟我太弱,ovoovo

#include #include #include #include using namespace std; struct point { int x, y; void read() { scanf("%d%d", &x, &y); } }; struct edge { int t, v; edge *ne; }; typedef pair <int, int> dpr; const int maxn = 200003; int n, xo[maxn], yo[maxn], d[maxn]; point p[maxn]; edge ebuf_arr[maxn « 2], *ebuf(ebuf_arr), *head[maxn]; inline bool xCmp(const int& a, const int& b) { return p[a]. x < p[b]. x; } inline bool yCmp(const int& a, const int& b) { return p[a]....

比较无语的一天考试…老师说是很神奇的好题…然后发现是shoi…然后让rausen鉴定途中强行被剧透. 第一题能二分ovo然后边界写丑了do了个大die. 第二题线段树水水水. 第三题想了2个小时,发现我根本不会什么lucas定理啊.于是只好百度一下.哦,这不是水题嘛ovoovo 其实lucas定理以前肯定遇到过.不过自己太久没用就搞忘了.noi之前要把各种奇怪的定理和算法复习一下.不然万一考到就亏了啊ovoovo 晚上给adminpage里加了些东西. 所以我还是太弱了.

haha

mhy大爷多久之前开的坑啊ovo 这题的思路比较神.点分+fft.两个点会产生的贡献是1/(dist + 1).于是要知道长度为多少的链有多少条. 利用树分可以将∑深度降到O(n*log n)的级别.原因很明显啊. 然后就用fft来求就好喽.反正是double也懒得用数论了.然后找了wyf的程序随便就拍出一组末位不等,也没用long double.居然能过太神奇了. 总复杂度O(n*log2n).然后莫名其妙就拿了rank1好开心啊.

#include #include #include #include using namespace std; #define float_t __float_t typedef double float_t; #define _f (float_t) struct cplx { float_t r, i; cplx() {} cplx(float_t ro, float_t io) { r = ro, i = io; } }; inline cplx operator +(const cplx& a, const cplx& b) { return cplx(a. r + b. r, a. i + b. i); } inline cplx operator -(const cplx& a, const cplx& b) { return cplx(a....

#include #include #include using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxn = 1003; const int maxm = 10003; const dint dinf = 0x3f3f3f3f3f3f3f3fll; int n, m, ne[maxn]; dint a[maxm][maxn]; void pivot(int e, int p) { int fr(n + 1); for (int i = n; i >= 0; – i) if (a[p][i]) { ne[fr] = i; fr = i; } ne[fr] = -1; a[p][e] = -1; for (int i = 0; i <= m; ++ i) if (i !...

simplex第一题.这玩意是不是拖得太久了啊ovo记得初中买算导的时候就想学它… simplex的思路其实比较简单.先找标号最小的目标函数中系数为正的变量.选择约束最紧的限制条件.通过这个条件来换元.直到消光. 感觉好神奇啊然而为啥啊ovoovo 然而线性规划的条件是≤而求的是目标函数的max.和这题的式子刚好相反啊. 然后神奇的东西是,对偶.强行把矩阵转制,然后把大小于符号取反,求出来的目标式max就是原问题的min.为啥啊Ovo算导上的证明也能看? 然后就是一个类似于高消的东西.据说跑得比较快. 另一个神奇的事情是在这道题里面因为奇怪的系数所以所有变量的系数都是+-1或者0.于是可以不用double强行写.开心. 然后网上的某份代码似乎会把无解的情况搞错hah 然而第一遍自己也有地方写丑… 这种东西还要再练练.