2018南京

Magical Girl Haze

bfs记忆化搜索
设dis[v][c]是走到v点，用掉了c次机会的最短路距离，比最短路问题多了一维
exd记录已经被扩展过的状态 
#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxn (200000+10)
#define maxm (1000000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int head[maxn],to[maxn],pre[maxn],tot;
ll dis[maxn][11],l[maxn];
int n,m,k;
void adde(int u,int v,ll c)
{
	to[++tot]=v,pre[tot]=head[u],head[u]=tot,l[tot]=c;
}
struct node
{
	int to;
	ll len;
	int step;
};
struct cmp
{
	bool operator()(node a,node b)
	{
		if(a.len!=b.len)return a.len>b.len;
		else return a.step>b.step;
	}
};
priority_queue<node,vector<node>,cmp>Q;
bool exd[maxn][11];
void dij()
{
	CLR(exd);while(!Q.empty())Q.pop();
	INF(dis);for(int i=0;i<=k;i++)dis[1][i]=0;
	Q.push(node{1,0,0});
	while(!Q.empty())
	{
		node p=Q.top();Q.pop();
		int u=p.to;
		ll len=p.len;
		int st=p.step;
		if(exd[u][st])continue;
		exd[u][st]=1;
		for(int i=head[u];i;i=pre[i])
		{
			int v=to[i];
			if(st<k&&!exd[v][st+1]&&dis[v][st+1]>len)
			{
				dis[v][st+1]=len;
				Q.push(node{v,len,st+1});
			}
			if(!exd[v][st]&&dis[v][st]>len+l[i])
			{
				dis[v][st]=len+l[i];
				Q.push(node{v,len+l[i],st});
			}
		}
	}
}
int main()
{
	int ttt;RD1(ttt);while(ttt--)
	{
		CLR(head);tot=0;
		RD3(n,m,k);for(int i=1;i<=m;i++)
		{
			int u,v;ll c;RD2(u,v);RDL1(c);
			if(u==v)continue;
			adde(u,v,c);
		}
		dij();
		printf("%lld\n",dis[n][k]);
	}
	return 0;
}
/*
1
3 5 0
1 2 1
2 3 2
2 3 3
2 3 1
1 3 100
*/

The writing on the wall

巧妙计数问题，按子矩形的某个顶点（代码里是左下角）枚举
总体思路：
关键优化：随着矩形宽度增加，以某一点为左下角的矩形能达到的高度递减
同时用h[]缓存该列的最高高度 
#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxn (200000+10)
#define maxm (1000000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
bool mp[100005][105];
int n,m,k;
int h[105];
int main()
{
	int ks=1;
	int ttt;RD1(ttt);while(ttt--)
	{
		CLR(mp);CLR(h);RD3(n,m,k);
		ll ans=0;
		while(k--){
			int x,y;RD2(x,y);mp[x][y]=1;
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)if(mp[i][j])h[j]=i;
			for(int j=1;j<=m;j++)
			{
				int Minh=inf;
				for(int c=j;c<=m;c++)
				{
					Minh=min(Minh,i-h[c]);
					ans+=Minh;
				//	cout<<ans<<endl;
				}
			}
		}
		printf("Case #%d: %lld\n",ks++,ans);
	}
	return 0;
}