刷题记录（NC16645 [NOIP2007]矩阵取数游戏，NC207781 迁徙过程中的河流，NC235953 最大m个子段和）

NC16645 [NOIP2007]矩阵取数游戏

题目链接

关键点：

1、答案会大于2的80次方，要采用特殊的输入和输出，以及快速幂的运算

2、从取数规则可以看出，每次取一行，计算每行的得分后算总和，那么说明各行间的取数互不相干，那么我们就可以计算每行取数的最大值，然后相加

3、对于每行的计算，取方程dp[i][j],为该行取i-j区间内的数，所能得到的最大值，因为每次只能从首尾来取数，

因此dp[i][j] = max(dp[i+1][j]+t[当前行][i]*(2, n次方)， dp[i][j-1]+t[当前行][j]*(2, n次方));

对于这个n，因为我们求一行的最大值，是从小区间到大区间，而对于大区间的范围，无疑是第一次取的时候，区间越小，当前已经取的次数就越多，所以n = m(总列数)-len(当前区间范围)+1,是先算的最后一次取的数。

4、答案就为每行求出的dp首位区间的最大值相加，注意点：当更新当前行时，dp要重新赋值为0

完整代码：

# include 
using namespace std;
typedef __int128 ll;
int n, m;
ll ju[100][100];
ll ans = 0;
ll dp[100][100];
ll read()
{
    ll s=0, w=1;
    char ch = getchar();
    while (ch<'0' || ch>'9')
    {
        if (ch=='-')
            w=-w;
        ch = getchar();
    }
    while (ch>='0'&&ch<='9')
    {
        s = s*10+ch-'0';
        ch = getchar();
    }
    return s*w;
}
void print(ll x)
{
    if (x<0)
    {
        putchar('-');
        x = -x;
    }
    if (x/10)
        print(x/10);
    putchar(x%10+'0');
}
ll quick(ll x, ll a)
{
    ll ans = 1;
    while (a)
    {
        if (a&1)
            ans*=x;
        x*=x;
        a>>=1;
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
            ju[i][j] = read();
    }
    for (int t=1; t<=n; t++)
    {
        memset(dp, 0, sizeof(dp));
        for (int len=1; len<=m; len++)
        {
            for (int i=1; i+len-1<=m; i++)
            {
                int j = i+len-1;
                dp[i][j] = max(dp[i+1][j]+ju[t][i]*quick(2, m-len+1), dp[i][j-1]+ju[t][j]*quick(2, m-len+1));
            }
        }
        ans += dp[1][m];
    }
    print(ans);
    
    return 0;
}

NC207781 迁徙过程中的河流

题目链接

关键点：

1、通过观察可以发现，当人数大于等于三人时，我们需要有人将船给开回来，那么要使时间花费最少，我们就派划船时间最少的来担任划船的角色

2、对于还剩一个人，和剩两个人的情况是不同的。还剩一个人时，我们只要派花费时间最少的来划船接剩下的人，而剩下两个人时，我们可以从案例中发现，可以先让最少的回来，然后让剩下的两个人划回去，再让花费第二少的回来接花费最少的回去

3、设dp[i],表示接前i个人所花费的最少时间，设花费最少的时间为t[1], 第二少的为t[2],a[i]为第i个划船时间

dp[i] = min(dp[i-1]+t[1]+a[i], dp[i-2]+t[1]+a[i]+t[2]+t[2]);

最终答案即为dp[n(总人数);

完整代码：

# include 
using namespace std;
int n;
int t[100000+10];
int dp[100000+10];//表示前i个过河的最少花费
int main()
{
    cin>>n;
    for (int i=1; i<=n; i++)
        cin>>t[i];
    sort(t+1, t+1+n);
    dp[1] = t[1];
    dp[2] = t[2];
    for (int i=3; i<=n; i++)
    {
        dp[i] = min(dp[i-1]+t[1]+t[i], dp[i-2]+t[1]+t[i]+t[2]+t[2]);
    }
    cout<
    
    return 0;
}

NC235953 最大m个子段和

题目链接

关键点：

1、每次选则当前第i个数，要么将其最为上一个字段的一部分，要么作为一个新的字段

2、对于最为上一个字段的一部分很好解决，那么如何取得最为一个新的字段的最大值呢，那么我们就要算出上一个字段的最大值然后加上当前数即可

3、dp[i]表示取前i个数所能得到的最大值，maxx[i]，表示第i个字段取前i个数的最大和,那么

dp[i] = max(dp[i-1]+a[i], last[i-1]+a[i]);

4、题目中给出，每个字段的长度至少为一，所以i每次循环要从当前字段的个数开始

5、对于last数组的计算，每次在计算出dp[i]时，我们更新一次last数组，加上当前的dp来更新

6、对于答案，我们遍历一遍dp数组，取最大值，因为对于给出的数字，不一定每一个都要选上

完整代码：

# include 
using namespace std;
typedef long long ll;
int n, m;
ll ans;
const int N = 1000000+10;
ll a[N];
ll maxx[N];
ll dp[N];//表示前i个数组成j个不相交的字串，所得的最大值
int main()
{
    cin>>n>>m;
    for (int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    memset(dp, -0x3f, sizeof(dp));
    for (int i=1; i<=m; i++)
    {
        for (int j=i; j<=n; j++)
        {
            dp[j] = max(dp[j-1]+a[j], maxx[j-1]+a[j]);
        }
        for (int j=i; j<=n; j++)
            maxx[j] = max(maxx[j-1], dp[j]);
    }
    for (int i=1; i<=n; i++)
        ans = max(ans, dp[i]);
    cout<
    
    return 0;
}