小鸟数据个人洛谷练习极简题解

P11242

碧树：叶子越远，枝干越长，已有的枝干再长一片叶子不影响枝干长度，最终就是枝干的长度加上叶子的总数。枝干总长取决于最远的那片叶子，叶子的总数题目中已经提供。

P11248

矩阵移动：三层循环，最内层循环k表示分别修改0、1、2、3...个问号时的最优解。

参考程序：

#include <bits/stdc++.h>
using namespace std;

int t,n,m,x,dp[505][505][505];
string s[505];

int main(){
    freopen("input.in","r",stdin);
    freopen("input.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&x);
        for(int i=1;i<=n;i++){
            cin >> s[i];
            s[i]=" "+s[i];
        }
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                for(int k=0;k<=x;k++){
                    dp[i][j][k]=(s[i][j]=='1')+max(dp[i-1][j][k],dp[i][j-1][k]);
                    if(k>0&&s[i][j]=='?')dp[i][j][k]=max(dp[i][j][k],1+max(dp[i-1][j][k-1],dp[i][j-1][k-1]));
                    cout << dp[i][j][k];
                }
                //cout << endl;
            }
            cout << endl << endl;
        }

        int ans=0;
        for(int i=0;i<=x;i++)
            ans=max(ans,dp[n][m][i]);
        printf("%d\n",ans);
    }
    return 0;
}

P1862

输油管道问题: 中位数又称中值，英语为Median，是按顺序排列的一组数据中居于中间位置的数，统计学中的专有名词，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，通常取最中间的两个数值的平均数作为中位数。

因为平均数容易受到极端数值的影响，比如国民生产总值，又比如一个公司的平均收入，领导层可能占据了收入的大头，人均后几万的收入并不能准确描述一个公司的普通员工收入。在这道题目中，排序找到中位，然后以中位为中心，累计首尾相减差值即可。

P11308

茫茫的不归路: 小队人数大于队伍上限，则必然为“Divide”，接下来取一个均值（向下取整），均值人数平均分配时，可插入人数最多的情况，如最差情况时，均值加拟插入小队的总和仍不超过队伍上限，则为“Together”，否则就只能是听天由命的“Chance”了。