10.8总结

· · 个人记录

T1

直接爆搜可以狂砍10pts，然后加上优化去重在每次选的时候选比上一个答案更大的可以优化到30pts
正解思路：今天dp专题测肯定是用dp来写啦（）
dp状态：dp[i][cnt]表示设i为特殊城市，并且前面有了cnt个城市是特殊城市的贡献最小值 首先在输入的时候就预处理n个城市到其他城市的距离，给dp[j][1]赋初始值为(x[i]-j)^2*c[i]
然后开始推式子，按照上文枚举第i个城市和前面有cnt个城市，然后由于不知道上一个城市，于是我们另外枚举j，计算从j到i会产生多少贡献，即为下列公式

其中x是（l,r）中大于（l+r）/2的坐标，pos[x]表示编号为x的城池人数
然后我们开始化简这个式子，拆开后面的式子可以变成

如果设大于mid的城池坐标为x1,x2...xn就可以给后面的答案整体化简为

后面的两个公式可以直接用后缀进行维护 要注意的是他没说每个x[i]不同，就默认有几个点在x[i]上 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 507;
int x[maxn],c[maxn];
int n,k;
int dp[maxn][maxn],pos[maxn];
int sum[maxn],sum_x[maxn];
signed main() {
    cin>>n>>k;
    for(int i=0;i<256;i++) {
        for(int j=0;j<256;j++) {
            dp[i][j]=1e18;
        }
        dp[i][1]=0;
    }
    for(int i=0;i<n;i++) {
        int x,c;
        cin>>x>>c;
        pos[x]+=c;
        for(int j=0;j<256;j++) {
            dp[j][1]+=(x-j)*(x-j)*c;
        }
    }
    for(int i=255;i>=0;i--) {
        sum[i]=pos[i]+sum[i+1];
        sum_x[i]=pos[i]*i+sum_x[i+1];
    }
    for(int i=0;i<256;i++) {
        for(int j=0;j<i;j++) {
            for(int cnt=2;cnt<=k;cnt++) {
                int mid=(i+j)/2+1;
                dp[i][cnt]=min(dp[i][cnt],dp[j][cnt-1]+2*(j-i)*sum_x[mid]+(i*i-j*j)*sum[mid]);
            }
        }
    }
    int ans=1e18;
    for(int i=0;i<256;i++) {
        ans=min(ans,dp[i][k]);
    }
    cout<<ans;
    return 0;
}

T2

如图管道只有四种摆放方式

首先我们横向来看，排列组合只有（1,2），（1,4），（2,3），（3,4）这四种，每一个管子距离上一个只有两种排列，竖方向同理，而我们则可以拆成2维，用一维模拟上一个管子的上一个状态，然后按照子序列dp来写就行了，总体而言比较板子，重点是要发现因为有这两种情况

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+7;
int a[maxn][maxn];
int dp[maxn][2];
int n,m; 
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin>>a[i][j];
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)  {
        memset(dp,0,sizeof(dp));
        for(int j=1;j<=m;j++) {
            dp[j][0]=max(dp[j-1][0],dp[j-1][1]);
            if(j!=1) {
                dp[j][1]=dp[j-1][0]+max(0,a[i][j]+a[i][j-1]);
            }
        }
        sum+=max(dp[m][0],dp[m][1]);
    }
    for(int j=1;j<=m;j++) {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++) {
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
            if(i!=1) {
                dp[i][1]=dp[i-1][0]+max(0,a[i][j]+a[i-1][j]);
            }
        }
        sum+=max(dp[n][0],dp[n][1]);
    }
    cout<<sum<<'\n';
    return 0;
}