Category: 动态规划

题目传送门：http://codeforces.com/contest/713/problem/C

我™之前做过这原题！然而考试的时候没想到怎么做QAQ

I well vegatable are!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3000+9;
const LL INF = 1e15;

int arr[N],hash[N],n,tot;
LL f[N][N],MN[N]; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

#define update(x,y) (x=((x)==-1||(y)<(x)?(y):(x)))
#define abs(x) ((x)>0?(x):-(x))

int main(){
	n = read(); 
	for (int i=1;i<=n;i++) hash[i] = arr[i] = read() - i;
	sort(hash+1,hash+1+n); tot = unique(hash+1,hash+1+n) - hash - 1;
	for (int i=1;i<=n;i++) memset(f[i],-1,sizeof(f[i])), MN[i] = -1;
	for (int i=1;i<=n;i++) {
		LL best = INF;
		for (int j=1;j<=tot;j++) {
			if (~f[i-1][j]) best = min(best, f[i-1][j]);
			update(f[i][j],best+abs(arr[i]-hash[j]));
		}
	} 
	LL vout = INF;
	for (int i=1;i<=tot;i++) if (~f[n][i])
		vout = min(vout, f[n][i]);
	cout<<vout; 
	return 0;
}

至于为什么减去下标答案不会变？
我们可以考虑差分序列啦！

—– UPD 2016.9.14 —–
这题看策爷的代码，可以用左偏树搞到O(nlogn)

原来这个题目可以贪心！
考虑最后的样子，一定长这样：

加入一个堆，其中位数不满足整体不减的话，即与左边的堆合并
为什么这么贪心的是对的呢？因为不管你砍哪一步分开，那一部分的差距都会更大，即不可能成为最优解

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3962

这个玩意，貌似可以暴力？
预处理出斜着的线上的点有多少，这样在暴力转移的时候，可以做到O(1)
然后就是写代码的事情了，然而写了两个小时了，没写出来QAQ
弃疗………..

—– 2016.9.6 更新 —–
耐着性子码完了代码
为什么觉得线段求交点常数大？
为什么要作死直接分类讨论 (╯‵□′)╯︵┻━┻

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 1000+9;

int n,m,q,sz,head[N],vout,X,Y;
int mat[N][N],f[2][N][N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

inline void prework(){
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) f[0][i][j] = f[0][i-1][j-1] + mat[i][j];
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) f[1][i][j] = f[1][i+1][j-1] + mat[i][j]; 
}
 
inline int pro(int x1, int y1, int x2, int y2, int t) {
	int ret = 0;
	if (!t) {
		x2--; y2--;
		if (x1 < 1 || y1 < 1) ret += 0;
		else if (x1 <= n && y1 <= m) ret += f[t][x1][y1];
		else if (x1 > n) ret += (y1-(x1-n)<=m && y1-(x1-n)>=1)? f[t][n][y1-(x1-n)]: 0;
		else ret += (1<=x1-(y1-m) && x1-(y1-m)<=n)? f[t][x1-(y1-m)][m]: 0; 
		
		if (x2 < 1 || y2 < 1) ret -= 0;
		else if (x2 <= n && y2 <= m) ret -= f[t][x2][y2];
		else if (x2 > n) ret -= (y2-(x2-n)<=m && y2-(x2-n)>=1)? f[t][n][y2-(x2-n)]: 0;
		else ret -= (1<=x2-(y2-m) && x2-(y2-m)<=n)? f[t][m][2-(y2-m)]: 0;
	} else {
		x2++; y2--;
		if (x1 > n || y1 < 1) ret += 0;
		else if (x1 >= 1 && y1 <= m) ret += f[t][x1][y1];
		else if (x1 < 1) ret += (y1-(1-x1)>=1 && y1-(1-x1)<=m)? f[t][1][y1-(1-x1)]: 0;
		else ret += (x1+(y1-m)>=1 && x1+(y1-m)<=n)? f[t][x1 + (y1 - m)][m]: 0;
		
		if (x2 > n || y2 < 1) ret -= 0;
		else if (x2 >= 1 && y2 <= m) ret -= f[t][x2][y2];
		else if (x2 < 1) ret -= (y2-(1-x2)>=1 && y2-(1-x2)<=m)? f[t][1][y2 -(1-x2)]: 0; 
		else ret -= (1<=x2+(y2-m) && x2+(y2-m)<=n)? f[t][x2+(y2-m)][m]: 0;
	} return ret;
} 

inline void solve(int lim){
	vout = 0; X = 1; Y = 1;
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++)
		if (i + j > lim + 2) break;
		else vout += mat[i][j];
	head[1] = vout; int tmp = vout;
	
	for (int j=1;j<=m;j++) {
		for (int i=1;i<n;i++) { 
			tmp += pro(i+lim+1,j,i+1,j-lim,0); // ¨J 
			tmp -= pro(i,j+lim,i-lim,j,0);     // ¨L 
			tmp += pro(i+1,j+lim,i+lim+1,j,1); // ¨K 
			tmp -= pro(i-lim,j,i,j-lim,1);     // ¨I 
			if (i + lim + 1 <= n) tmp -= mat[i+lim+1][j];
			if (i - lim >= 1) tmp += mat[i-lim][j];
			if (tmp > vout) vout = tmp, X = i+1, Y = j;
		}
		if (j < m) {
			tmp = head[j];
			tmp += pro(1,j+lim+1,1+lim,j+1,1);//¨K 
			tmp += pro(1,j+lim+1,1-lim,j+1,0);//¨L 
			tmp -= pro(1+lim,j,1,j-lim,0);//¨J 
			tmp -= pro(1-lim,j,1,j-lim,1);//¨I 
			if (j + lim + 1 <= m) tmp -= mat[1][j+lim+1];
			if (j - lim  >= 1) tmp += mat[1][j-lim];
			if (tmp > vout) vout = tmp, X = 1, Y = j+1;
			head[j+1] = tmp;
		}
	}	 
	
}

inline void init(int w){
	memset(f,0,sizeof(f));
	memset(mat,0,sizeof(mat));
	printf("Case %d:\n",w);
}

int main(){
	for (int T=1;scanf("%d%d",&n,&m) && n && m;T++) { 
		init(T); sz = read(); q = read();  
		for (int i=1,x,y;i<=sz;i++) x = read(), y = read(), mat[x][y]++;
		prework(); 
		for (int k=1;k<=q;k++) {
			solve(min(m+n,read()));
			printf("%d (%d,%d)\n",vout,X,Y);
		} 
	}
	return 0;
}

然而DZY告诉我们，这货可以变成正方形？
参见：http://dzy493941464.is-programmer.com/posts/86498.html
仔细想了一想：我们可以通过将整个图旋转45°，然后重新编号，然后就变成了正方形？
然后就是很常规的滑动窗口了？

—– UPD 2016.6.9 —–
坐标旋转的代码

#include<bits/stdc++.h>
using namespace std;

const int N = 2000+9;
int n,k,q,mat[N][N],sta[N],sum[N][N],MX;

inline int read(){
	char c=getchar(); int ret=0,f=1; 
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} 
	return ret*f;
}

#define SUM(x,y) sum[max(0,min(x,MX))][max(0,min(y,MX))]
inline void solve(int lim) { int vout = 0;
	for (int j=1;j<=n;j++) for (int i=1,x,y;i<=n;i++) x = sta[i]-j+1, y = i+j-1,
		vout = max(vout, SUM(x+lim,y+lim) + SUM(x-lim-1,y-lim-1) - SUM(x+lim,y-lim-1) - SUM(x-lim-1,y+lim));
	printf("%d\n",vout);
}

int main(){
	n = read(); k = read(); q = read(); MX = n * 2 - 1; 
	sta[1] = n; for (int i=2;i<=n;i++) sta[i] = sta[i-1] + 1;
	for (int i=n+1;i<=n*2-1;i++) sta[i] = sta[i-1] - 1;
	for (int i=k,x,y;i;--i) x = read(), y = read(), mat[sta[x]-y+1][x+y-1] = 1;
	for (int j=1;j<=MX;j++) for (int i=1;i<=MX;i++) sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + mat[i][j];
	for (int i=1;i<=q;i++) solve(read());
	return 0;
} 

题目传送门：http://codeforces.com/contest/710/problem/E
官方题解：http://codeforces.com/blog/entry/46761

这题，做法很多:
有简单粗暴型：http://www.cnblogs.com/Coolxxx/p/5797798.html
也有优雅递推型：http://blog.csdn.net/qq_33184171/article/details/52289905
我是第二种，不过第二种有一个东西需要证明：至少存在一组最优解使得-1操作至多连续进行1次

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 1e7+9; 

int n,x,y;
LL f[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

int main(){
	n = read(); x = read(); y = read();
	f[1] = x; for (int i=2;i<=n;i++) {
		f[i] = f[i-1] + x;
		if (i & 1) f[i] = min(f[i], f[i+1>>1] + x + y);
		else f[i] = min(f[i], f[i>>1] + y);
	}
	printf("%I64d\n",f[n]);
	return 0;
}

题目传送门：http://codeforces.com/contest/703/problem/E
官方题解：http://codeforces.com/blog/entry/46434
中文题面：http://www.cnblogs.com/dramstadt/p/5759206.html

题解的话，看官方题解就好
唯一想吐槽的就是：CF上居然卡常！
看看这通过的名单，™大家都是压线过的啊

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int M = 7000;
const int N = 1000+9;
const int INF = 10000000;

LL k,Hash[M],buf[M],sum[2][M];
int n,cnt,f[2][M],nxt[N][M],vout[N][M];
unordered_map<LL,int> idx;

inline LL read(){
	char c=getchar(); LL ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

inline LL find(LL w){
	int l=1, r=cnt, mid;
	while (l <= r) {
		mid = l + r >> 1;
		if (Hash[mid] == w) return mid;
		else if (Hash[mid] < w) l = mid+1;
		else r = mid-1;
	} 
}

inline void Decomposision(LL num) {
	LL lim = sqrt(num); if (lim*lim != num) lim++;
	for (int i=1;i<=lim;i++) if (num % i == 0) buf[++cnt] = i, buf[++cnt] = num/i;
	if (lim*lim == num) cnt--;
	for (int i=1;i<=cnt;i++) Hash[i] = buf[i];
	sort(Hash+1,Hash+1+cnt);
	for (int i=1;i<=cnt;i++) idx[buf[i]] = find(buf[i]);
}

inline LL GCD(LL a, LL b){
	while (b) {
		a = a%b;
		swap(a, b);
	}
	return a;
}

inline void SPJ(){
	if (k == 1) {
		LL vout = 1, tmp = read();
		for (int i=2;i<=n;i++) {
			LL t1 = read(); if (t1 < tmp) 
			tmp = t1, vout = i;
		} cout<<1<<endl<<vout; exit(0);
	}
}

int main(){
	n = read(); k = read(); SPJ();
	Decomposision(k); 
	for (int i=2;i<=cnt;i++) f[0][i] = INF; int now=1,pre=0;
	for (int i=1;i<=n;i++,pre^=1,now^=1) {
		LL w = read(), t2, t3 = GCD(w,k);
		for (int j=2,tmp,t1;j<=cnt;j++) {
			tmp = f[pre][t1=idx[Hash[j]/GCD(Hash[j],t3)]]+1;
			t2 = w + sum[pre][t1];
			if (f[pre][j] > tmp  || (f[pre][j] == tmp && t2 <= sum[pre][j])) 
				f[now][j] = tmp, nxt[i][j] = t1, vout[i][j] = i, sum[now][j] = t2;
			else f[now][j] = f[pre][j], nxt[i][j] = j, vout[i][j] = 0, sum[now][j] = sum[pre][j];
		}
	}
	if (f[pre][cnt] == INF) printf("-1\n");
	else {
		printf("%d\n",f[pre][cnt]);
		LL w = cnt, stp = n;
		while (w) {
			if (vout[stp][w]) printf("%d ",vout[stp][w]);
			w = nxt[stp][w]; stp--;
		}
	}
	return 0;
}

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1505

仍然是决策单调性QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 100+9;
const int MX = 100;

double f[2][MAXN][MAXN],k1,k2;
int n,m,sz[MAXN],sta=1;

#define cal_up(l,r) (k1*((r)-(l))*((r)-(l)))

inline double cal_down(int l, int r, int t){
	int len = r-l, tmp = 0; double ret = 0;
	for (int i=1;i<=t;i++) sz[i] = len/t, tmp += sz[i];
	while (tmp < len) for (int i=1;i<=t && tmp < len;i++) sz[i]++, tmp++;
	for (int i=1;i<=t;i++) ret += k2*sz[i]*sz[i];
	return ret; 
}

inline void Dynamic_Programing(int w, int t){
	for (int i=1;i<=MX;i++) memset(f[w][i],0,sizeof(f[w][i]));
	for (int j=1,t1=1,t2=1;j<=n;j++,t1=1,t2=1) for (int i=1;i<=MX;i++) if (j <= i) {
		for (int h=max(1,t1-3);h<i;h++) for (int g=max(t2-3,1);g<j;g++) if (f[t][h][g]) {			
			double tmp = f[t][h][g] + cal_up(h,i) + cal_down(h,i,j-g);
			if (!f[w][i][j] || f[w][i][j] > tmp) f[w][i][j] = tmp, t1=h, t2=g;
		}
	}
}

int main(){
	scanf("%lf%lf%d%d",&k1,&k2,&m,&n);
	for (int i=1;i<=MX;i++) for (int j=1,lim=min(n,i);j<=lim;j++)
		f[1][i][j] = cal_up(0,i) + cal_down(0,i,j);
	for (int k=2;k<=m;k++,sta^=1) Dynamic_Programing(sta^1,sta);
	printf("%.1lf\n",f[sta][MX][n]);
	return 0;
} 

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2216

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int MAXN = 500000+9;
const double EPS = 1e-8;

int arr[MAXN],n,f[MAXN],l[MAXN],r[MAXN],que[MAXN],head,tail;

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret;
}

inline double cal(int a, int b){
	return sqrt(abs(a-b)) + arr[a];
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) arr[i] = read();
	
	l[tail=head=1] = 1; r[1] = n; que[1]=1;
	for (int i=2;i<=n;i++) {
		l[tail]++;
		while (tail <= head && r[tail] < l[tail]) tail++;
		f[i] = max(f[i], int(ceil(cal(que[tail],i))+EPS));
		if (cal(i,r[head]) < cal(que[head],r[head])) continue;
		else {
			while (tail <= head && cal(i,l[head]) > cal(que[head],l[head])) head--; 
			if (tail <= head) {
				int ls=l[head],rs=r[head],mid,ans=r[head]-1;
				while (ls <= rs) {
					mid = ls + rs >> 1;
					if (cal(i,mid) < cal(que[head],mid)) ls = mid+1;
					else ans = mid, rs = mid-1;
				}
				r[head] = ans; l[++head] = ans+1; r[head] = n; que[head] = i;
			} else que[++head] = i, l[head] = i, r[head] = n;
		}
	}
	
	l[tail=head=1] = n; r[1] = 1; que[1]=n; que[0]=1;
	for (int i=n-1;i;i--) {
		l[tail]--;
		while (tail <= head && r[tail] > l[tail]) tail++;
		f[i] = max(f[i], int(ceil(cal(que[tail],i))+EPS));
		if (cal(i,r[head]) < cal(que[head],r[head])) continue;
		else {
			while (tail <= head && cal(i,l[head]) > cal(que[head],l[head])) head--; 
			if (tail <= head) {
				int ls=l[head],rs=r[head],mid,ans=r[head]+1;
				while (ls >= rs) {
					mid = ls + rs >> 1;
					if (cal(i,mid) < cal(que[head],mid)) ls = mid-1;
					else ans = mid, rs = mid+1;
				}
				r[head] = ans; l[++head] = ans-1; r[head] = 1; que[head] = i;
			} else que[++head] = i, l[head] = i, r[head] = 1;
		}
	}
	
	for (int i=1;i<=n;i++) printf("%d\n",max(f[i]-arr[i],0));
	return 0;
}

题目传送门： http://www.lydsy.com/JudgeOnline/problem.php?id=1563

决策单调性

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define LD long double
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int MAXN = 100000+9;
const LD EPS = 1e-8;
const LD MX = 1e18+EPS;

int arr[MAXN],n,L,p,l[MAXN],r[MAXN],que[MAXN],head,tail;
LD f[MAXN];
char pat[50];

inline LD cal(int a, int b){
	return f[b]+pow((LD)abs(arr[a]-arr[b]+a-b-1-L),p);
}

int main(){
	int T; cin>>T;
	while (T--) {
		scanf("%d%d%d",&n,&L,&p);
		for (int i=1;i<=n;i++) scanf("%s",pat+1), arr[i] = arr[i-1] + strlen(pat+1);
		l[head=tail=0] = 1; r[0] = n; f[0] = 0; que[0] = 0;
		for (int i=1;i<=n;i++) {
			while (r[tail] < i) tail++;
			f[i] = cal(i,que[tail]);
			if (cal(r[head],que[head]) < cal(r[head],i)) continue;
			else {
				while (head >= tail && cal(l[head],que[head]) >= cal(l[head],i)) head--;
				if (head >= tail) {
					int ls=l[head],rs=n,ans=0,mid;
					while (ls <= rs) {
						mid = ls + rs >> 1;
						if (cal(mid,que[head]) < cal(mid,i)) ans = mid, ls = mid+1;
						else rs = mid-1;
					}
					r[head] = ans; l[head+1] = ans+1; r[head+1] = n;
				} else l[head+1] = 1, r[head+1] = n;
				que[++head] = i; 
			}	
		}
		if (f[n] <= MX) printf("%lld\n",(LL)(f[n]+EPS));
		else printf("Too hard to arrange\n");
		puts("--------------------");
	}
	return 0;
}