A
首先，答案必然是整数，且医院一定均设置在村庄位置。
然后对于所有村庄按照位置排序。
n2k做法：
令 cacl[i][j]代表在所有下标为 i 至 j 直接的村庄只设置一所医院的最短距离和，dp[i][j] 表示在前 i 个村庄设置 j 所医院的最短距离和，那么
dp[i][j]=min(dp[i][j],dp[k][j−1]+cacl[k+1][i]) k<inklogn做法：
我们发现在转移时是具有单调性的，即在设置的医院数字 j 固定的情况下，当村庄数 i 增加的时候，最小的值的决策点 k 一定是右移的。就可以优化上述转移了。
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define pll pair<long long,long long>
#define fer(i,a,n) for (int i=(a);i<=(n);++i)
#define notall(x) x.begin()+1,x.end()
#define all(x) x.begin(),x.end()
template<class T1, class T2>
void cmin(T1 &a, T2 b) {
a = min<T1>(a, b);
}
using ll=long long;
const ll inf=2e18;
void solve()
{
ll n,k;
cin>>n>>k;
vector<pll>pa(n+1);
fer(i,1,n){
auto&[p,a]=pa[i];
cin>>p>>a;
}
sort(notall(pa));
vector<vector<ll>>pre(n+1,vector<ll>(n+1,inf)),dp(n+1,vector<ll>(k+1,inf));
fer(i,1,n)
{
ll p=i,nowl=pa[i].second,nowr=0,nowsum=0;
auto caclnext=[&]()
{
ll pp=p,tmpl=nowl,tmpr=nowr,sum=nowsum,dis=pa[p+1].first-pa[p].first;
pp++,sum+=tmpl*dis-tmpr*dis,tmpr-=pa[pp].second,tmpl+=pa[pp].second;
return tuple{sum,tmpl,tmpr};
};
pre[i][i]=0;
fer(j,i+1,n)
{
nowr+=pa[j].second,nowsum+=pa[j].second*(pa[j].first-pa[p].first);
while(p<j)
{
auto[tmpsum,tmpl,tmpr]=caclnext();
if(tmpsum>=nowsum)break;
p++,nowsum=tmpsum,nowl=tmpl,nowr=tmpr;
}
cmin(pre[i][j],nowsum);
}
}
dp[0][0]=0;
fer(j,1,k)
{
//0 ~ z-1
vector<int>opt(n+2);
opt[0]=0,opt[n+1]=n-1;
function<void(int,int)>calc=[&](int l,int r)
{
if(l>r)return;
int mid=(l+r)/2;
fer(i,opt[l-1],opt[r+1])
if(dp[mid][j]>dp[i][j-1]+pre[i+1][mid])
dp[mid][j]=dp[i][j-1]+pre[i+1][mid],opt[mid]=i;
calc(l,mid-1),
calc(mid+1,r);
};
calc(1,n);
}
cout<<dp[n][k]<<'\n';
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)solve();
}
F
显然这个数据范围是假的，n+m−1>k的时候直接输出 0。
因为前面有各种颜色的点，无后效性显然不成立啊。
然后我们来愉快的状压搜索。
我们用fi,j,k表示在使用k种颜色情况下，走到(i,j)的方案数 。
这里有一个很重要的剪枝：对称性剪枝。
我们发现不同的颜色的作用是相同的。
所以如果从点(1,1)到(x,y)还有k种颜色没填，那么fx,y,count(k)是一个定值
代码：
#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;
ll m,n,k,a[20][20],num[20],f[20][20];
inline ll lowbit(ll x){
return x&(-x);
}
ll dfs(ll x,ll y){
if(y==m+1){
x++;
y=1;
}
if(x==n+1) return 1;
ll ret=0,d=-1,now=f[x-1][y]|f[x][y-1],c=0;
for(ll i=now; i; i-=lowbit(i)) c++;
if(m+n-x-y+1>k-c) return 0;
ll can=(~now)&((1<<k)-1);
for(ll i=can; i; i-=lowbit(i)){
ll temp=lowbit(i),t=log(temp+0.5)/log(2)+1;
if(a[x][y]==0||a[x][y]==t){
f[x][y]=now|temp;
num[t]++;
if(num[t]==1){
if(d==-1) d=dfs(x,y+1);
ret+=d;
}
else if(num[t]!=0) ret+=dfs(x,y+1);
ret%=MOD;
num[t]--;
}
}
return ret;
}
int main(){
scanf("%lld %lld %lld",&n,&m,&k);
if(n+m-1>k){
printf("0");
return 0;
}
for(ll i=1; i<=n; i++){
for(ll j=1; j<=m; j++){
scanf("%lld",&a[i][j]);
if(a[i][j]!=0) num[a[i][j]]++;
}
}
printf("%lld",dfs(1,1));
return 0;
}
K
搬运题，见 Problem - M - Codeforces
共 1 条回复
F题是CF293B