DP---NOI

飞镖

【题目描述】 小N 和小A 在玩扔飞镖游戏，NM的格子上每个格子有一个0~9 的数 字，因为他们技术都不是特别厉害，所以如果瞄准了(x,y)这个格子，就会 等概率打中以这个格子为中心的33 的格子。他们一共轮流投了K 轮飞 镖，每一轮都是小N 先投，投完后小A 投。小N 和小A 都十分聪明，他 们一定会选择最优的策略，小A 想知道他获胜的概率是多少呢（平局情况 视为小A 获胜0.5 局）？ 【输入数据】 第一行2 个整数N,M 接下来N 行每行M个整数表示这个格子的分数。 最后一个整数K 表示他们投的轮数。 【输出数据】 输出小A 获胜的概率，保留4 位小数。 【样例输入】 7 3 8 8 8 8 0 8 8 8 8 0 0 0 0 0 0 9 9 9 9 9 9 1 【样例输出】 0.5370 【数据范围】 30%的数据满足K≤2。 100%的数据满足N,M,K≤20。

题解

Ada 我们考虑一次操作，能影响这次操作决策的仅仅是两为选手的分差，于是可以用一个数组F[0..1][i][j]，表示当前轮到第1（2）个人操作时，还剩下j轮没有操作，当前两人分差时i的获胜概率。这样当j=0时可以直接算出F,然后考虑转移：枚举这个人选择的扔的地点是哪里，然后九个格子取平均（用之前已经算过的F，这时考虑分差的加减），然后对所有扔的地点取获胜概率的最大值即可。 时间复杂度：O（NM9K*K）

code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#define ll long long
#define lf double
#define cha 190
#define N 25
using namespace std;
int n,m,k,a[N][N];
int fx[10]={1,1,1,0,0,0,-1,-1,-1};
int fy[10]={1,0,-1,1,0,-1,1,0,-1};
lf f[N][400],g[N][400];//gÏÈÊÖ,fºóÊÖ 
inline int read(){
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}
int main() {
	freopen("ada.in","r",stdin);
	freopen("ada.out","w",stdout);
	n=read(),m=read();
	for(int i=1; i<=n; i++)	for(int j=1; j<=m; j++)	a[i][j]=read();
	k=read();
	f[0][cha]=0.5;
	for(int i=1; i<=9*k; i++) f[0][i+cha]=1.0;
	for(int i=1; i<=k; i++) { //ÂÖÊý 
		for(int j=-(k-i+1)*9; j<=(k-i+1)*9; j++) //·Ö²î·¶Î§ 
			for(int x=2; x<n; x++) //ö¾Ùµã 
				for(int y=2; y<m; y++) {
					lf res=0;
					for(int kk=0; kk<9; kk++)
						res+=f[i-1][j-a[x+fx[kk]][y+fy[kk]]+cha]; //ÖÜΧ9¸öµã 
					g[i][j+cha]=max(g[i][j+cha],1.0-res/9);
				}
	//¸´ÔÓ¶ÈO(20*20*9*2*20*20) 
		for(int j=-(k-i)*9; j<=(k-i)*9; j++)
			for(int x=2; x<n; x++)
				for(int y=2; y<m; y++) {
					lf res=0;
					for(int kk=0; kk<9; kk++)
						res+=g[i][j+a[x+fx[kk]][y+fy[kk]]+cha];
					f[i][j+cha]=max(f[i][j+cha],1.0-res/9);
				}
	}
	printf("%.4lf\n",1.0-f[k][cha]);
	return 0;
}

设计铁路

【题目描述】 A 省有一条东西向的公路经常堵车，为解决这一问题，省政府对此展 开了调查。调查后得知，这条公路两侧有很多村落，每个村落里都住着很 多个信仰c 教的教徒，每周日都会开着自家的车沿公路到B 地去“膜拜” 他们的教主，这便是堵车的原因。详细调查显示：这里总共有N 个村 落，并且它们都在B 地的东边。编号为i 的村落住有Ri 个信仰c 教的教 徒，距离B 地的距离为Ti（单位：公里）。 为解决这一问题，A 省政府决定在这条公路下修建一条地下快速铁路 来缓解交通，并沿线修建若干个车站（B 地会修建终点站，不算车站）。 每名教徒都会先往B 地方向开车（如果他所在村庄处恰好有车站就不必开 车了），到最近的一个快速铁路车站时换乘（如果直接开到B 地就不用换 乘了），再通过快速铁路到B 地。 但A 政府遇到一个难题：修建多少个车站以及在哪修建车站。一个修 建车站的方案中，如果修建过多的车站则会花费过多的钱，但修建的车站 少了或者修建的位置不对又会导致公路的拥堵。A 政府为了协调这两方 面，采用评分的方式来衡量一个方案的好坏（分数越大方案越坏）：每修 建一个车站会增加m 的分数，在某一次“膜拜”中（只考虑去，不考虑返 回），每导致1 个教徒开车行驶1 公里会增加1 分。 现请你设计一个修建车站的方案，使得分数最小。请输出这个最小的 分数。 【输入说明】 输入的第一行包含两个正整数n、m。 之后n 行每行两个正整数Ti、Ri。 【输出说明】 输出一个整数，表示最小的分数。 【样例输入】 4 20 25 3 5 3 25 2 20 5 【样例输出】 55 【数据范围】 对于20%的数据，n<=200； 对于60%的数据，n<=2000； 对于100%的数据，n<=40000，m<=2000000000，Ti<=1000000，Ri<=1000。

题解

Design 典型的动态规划，写出转移方程后可以看出能用斜率优化，直接套模板就好了。

code

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=4e5+5;
struct peo
{
	int pos,num;
}p[maxn];
int q[maxn],n,m;
long long dp[maxn],sum[maxn],ans;
double judge(int k,int j)
{
	return (double(dp[k]-dp[j])/double(p[k].pos-p[j].pos));
}
bool cmp(peo x,peo y)
{
	return x.pos<y.pos;
}
int main()
{
	freopen("design.in","r",stdin);
	freopen("design.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)	scanf("%d%d",&p[i].pos,&p[i].num);
	sort(p+1,p+1+n,cmp);
	for(int i=1;i<=n;i++)	sum[i]=sum[i-1]+p[i].num;
	q[0]=1;int l=0,r=1;
	for(int i=1;i<=n;i++)	dp[0]+=p[i].num*p[i].pos;
	for(int i=1;i<=n;i++)
	{
	    while(l<r&&judge(q[l+1],q[l])<=sum[i-1]-sum[n])	l++;
	    dp[i]=dp[q[l]]+m-(sum[n]-sum[i-1])*(p[i].pos-p[q[l]].pos);
	    while(l<r&&judge(i,q[r])<judge(q[r],q[r-1]))	r--;
	    q[++r]=i;
	}
	ans=0x3f3f3f3f3f3f3f3fll;
	for(int i=0;i<=n;i++)	ans=min(dp[i],ans);
//	printf("%lld\n",ans);
	cout<<ans<<endl;
	return 0;
}

双排序

【题目描述】 一个长方形的网格每个格子里有一个小写英文字母。我们称这个网格 是双排序(doubly sorted)的，当每一行从左到右都是不下降的，每一列从上 到下也是不下降的。在下面的例子中，前两个网格是双排序的，而后两个 不是。

abc ace aceg base def ade cdef base ghi bdg xxyy base

给你一个部分格子填了英文字母的网格。你的任务是计算有多少种方 式把剩下的格子填满，使所得网格是双排序的。答案可能很大，你只要输 出方案数对10007 取模的余数。 【输入数据】 第一行一个整数T，表示数据组数。接下来有T 组数据。每组数据的 第一行有两个整数R 和C，表示网格的行数和列数。接下来R 行，每行有 一个长度为C 的字符串，表示部分填写的网格。每个字符是一个小写英文 字母，或'.'（表示这个格子没有被填写）。 【输出数据】 对每组数据，输出一行。这行包含"Case #X: y"，X 是这组数据的编号 （从1 开始），y 是可能的双排序网格的个数，模10007。 【样例输入】 3 2 2 ad c. 3 3 .a. a.z .z. 4 4 .... .a.. .kf. .... 【样例输出】 Case #1: 23 Case #2: 7569 Case #3: 0 【数据范围】 T = 40 每个字符都是'.'或小写字母。 对于30%的数据（10s） 1 ≤ R, C ≤ 4 对于100%的数据（2min） 1 ≤ R, C ≤ 10 为了防止各位大神AK 完无聊，如果你这题第二个点的内存在64M。内，且时间在1min 内，将给你额外加40 分。

题解

Sort 考虑双排序的网格，从左上到右下不减，也就是说对与一个字母c，所有<=c的字母的轮廓线一定是一个从左下到右上的一条路径。然后可以用状态压缩维护这个路径，由于棋盘为10*10，那么这条路径包含10个(向右)和十个(向上)，总共个数为C(10,20)。为了避免重复转移，应按照行的顺序将轮廓线向右边推进。 时间复杂度：O（C(10,20)*N^2×26）

code

\\wxh大佬果然达成了附加40分的副本！！！
#include <cstdio>
#include <cstring>
#include <iostream>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define fill( x, y ) memset( x, y, sizeof x )
#define copy( x, y ) memset( x, y, sizeof x )
using namespace std;
typedef long long LL;
typedef pair < int, int > pa;
const int MAXN = 12;
const int MAXM = 200010;
const int MAXV = 1048577;
const int mod = 10007;
int n, m, h[MAXM], id[MAXV], id_cnt, dp[27][MAXM][MAXN], kth[MAXM][21], cas;
bool vis[27][MAXM][MAXN];
char ch[MAXN][MAXN];
inline void inc(int &x, int y) { x += y; if( x >= mod ) x -= mod; }
inline int dfs(int alpha, int S, int x)
{
	int &ret = dp[ alpha ][ S ][ x ];
	if( vis[ alpha ][ S ][ x ] ) return ret; vis[ alpha ][ S ][ x ] = 1;
	if( alpha == 26 ) return ret = ( S == id_cnt );
	if( x < m ) ret = dfs( alpha, S, x + 1 ); else ret = dfs( alpha + 1, S, 1 );
	int k = kth[ S ][ x ];
	if( k != n + m - 1 && !( h[ S ] & ( 1 << k + 1 ) ) )
	{
		int t = n + m - k - x;
		if( ch[ t ][ x ] == '.' || ch[ t ][ x ] == alpha + 'a' ) inc( ret, dfs( alpha, id[ h[ S ] ^ ( 1 << k ) ^ ( 1 << k + 1 ) ] , x ) );
	}
	return ret;
}
inline void solve()
{
	fill( vis, 0 ); id_cnt = 0;
	scanf( "%d%d", &n, &m );
	for( int i = n ; i ; i-- )
		scanf( "%s", ch[ i ] + 1 );
	for( int i = 0 ; i < ( 1 << n + m ) ; i++ )
		if( __builtin_popcount( i ) == m ) h[ id[ i ] = ++id_cnt ] = i;
	for( int i = 1 ; i <= id_cnt; i++ )
	{
		int S = h[ i ];
		for( int j = n + m - 1, t = 0 ; ~j ; j-- )
			if( S >> j & 1 )
				kth[ i ][ ++t ] = j;
	}
	printf( "Case #%d: %d\n", ++cas, dfs( 0, 1, 1 ) );
}
#define FIO "sort"
int main()
{
#ifdef wxh010910
	freopen( "data.in", "r", stdin );
#else
	freopen( FIO".in" , "r", stdin  );
	freopen( FIO".out", "w", stdout );
#endif
	int T;
	scanf( "%d", &T );
	while( T-- ) solve();
	return 0;
}