A
求出来到每座山的距离后,就可以计算出每只猫等待的时间与出发时间的关系。
如果出发时间为\(x\),求出来只猫的等待时间。这里用\(b_i\)表示第i只猫的等待时间。然后我们将这些时间排序。问题就转化为了,从m个有序的数中,选出p个,每个数字覆盖以其为开头的一段区间。这段区间的贡献为\(x\times num-sum\),其中x为当前选定的数字。\(num\)为覆盖区间的长度。\(sum\)为覆盖区间的数字和。
这样就可以得到一个\(m^2p\)的朴素dp。
\(f[i][j]\)表示选出i个点,覆盖前j个元素,最小贡献。
\(f[i][j]=\min\limits_{k=1}^i\{f[i-1][k - 1]+b[k]\times j+(j-k)\times b[k]-(sum[j]-sum[k]))\}\)
然后就很斜率优化了。。。
/*
* @Author: wxyww
* @Date: 2019-08-07 19:31:15
* @Last Modified time: 2019-08-07 19:49:05
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 50010,M = 1010;
#define int ll
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
ll sum[N];
int n,m,p,f[N],g[N],a[N];
ll b[N];
ll B(int x) {
return sum[x] - x * b[x] + g[x - 1];
}
bool cmp(int x,int y) {
return x > y;
}
int q[N];
int calc(int x,int y) {
return b[x] * y + B(x);
}
bool check(int p1,int p2,int p3) {
return 1ll * (B(p2) - B(p3)) * (b[p3] - b[p1]) > 1ll * (B(p1) - B(p3)) * (b[p3] - b[p2]);
}
main() {
n = read(),m = read(),p = read();
for(int i = 2;i <= n;++i) a[i] = a[i - 1] + read();
for(int i = 1;i <= m;++i) {
int x = read(),y = read();
b[i] = y - a[x];
}
sort(b + 1,b + m + 1,cmp);
for(int i = 1;i <= m;++i) sum[i] = sum[i - 1] + b[i];
memset(f,0x3f,sizeof(f));
f[0] = 0;
for(int j = 1;j <= p;++j) {
for(int i = 0;i <= m;++i) g[i] = f[i];
memset(f,0x3f,sizeof(f));
f[0] = 0;
int head = 1,tail = 0;
for(int i = 1;i <= m;++i) {
while(head < tail && check(q[tail],q[tail - 1],i)) --tail;
q[++tail] = i;
while(head < tail && calc(q[head + 1],i) <= calc(q[head],i)) ++head;
f[i] = calc(q[head],i) - sum[i];
}
}
cout<<f[m]<<endl;
return 0;
}
B
非常interesting的一道题。
考虑倒着做。用某大佬的话说就是"拔地鼠",只有当某个位置所在的行和列不含有除这个位置外的地鼠,这个位置才可以被"拔出来"。我们将其拔出来之后,将他所在的行和列都标记为灰色。表示可能为白色(有地鼠),也可能为黑色(无地鼠)。
然后开始bfs,将尽量多的点刷为灰色。
最后比较一下非灰色的点是不是与初始状态相同。
需要特判初始状态本就与终止状态相同的情况。还有,如果某一行和某一列都为灰色,那么他们的交点处初始必须是白色。否则就无法开始。
/*
* @Author: wxyww
* @Date: 2019-08-07 20:10:07
* @Last Modified time: 2019-08-07 20:26:25
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1010;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
char s1[N][N],s2[N][N];
int sum1[N],sum2[N],vis1[N],vis2[N],vis[N][N],col[N][N];
queue<pair<int,int> >q;
int main() {
int n = read(),m = read();
int bz = 0;
for(int i = 1;i <= n;++i) scanf("%s",s1[i] + 1);
for(int i = 1;i <= n;++i) scanf("%s",s2[i] + 1);
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j)
if(s1[i][j] != s2