2020_7_23

ABCDEFGH
A
题意：将几个相等的数，将其中的几个数每次减去同一个数，其中一个数没有处理。知道操作后的各个数。求最小次数及减数。
思路：减数为任意被减数前后的差的和之间的公共最大公约数。前缀相加依次求最大公约数。

B
题意：给出一个只含ab字符的字符串，每次可以修改一个字母，求修改多少次后，每个偶数长度前缀都有相同的a,b字符个数。求最小修改次数。
思路：这样的字符串每两个字符就只能有一个a一个b，求最小次数有点匪夷所思。

C
题意：给你若干个数(ai…an),并且bi=(i-1)*ai+1,你可以改变数组a的循序，求(bi…bn)之和的最小值及索引值循序。
思路：~~根据例子看出数组a是从大到小排列的。~~当i变大，(i+1)*ai也会变大 ,所以数组a需要从大到小排列。

D
题意：给出一张白色矩形的纸张，然后放两张黑色矩形纸张，分别知道他们的右上角及左下角坐标，判断是否从上面还能看到白色吗？
思路：题意比较简单，但是我的几何想象力不强，如果用暴力设置二维数组一定会超时，常识中判断的标准就是面积。通过两个矩形左下角右上角坐标的比较获取公共部分，然后求面积，并且减去重复的部分。

E
题意：给出一组数，两两相加，判断是否可能出现2048.
思路：这题操作和昨天刚补的题D. Unmerge一样，用完全背包就行。

F
题意：给出三个类型的数量a,b,c。其中一个完美的组至少含有前两个类型。求最大完美组数。
思路：如果min(a,b,c)!=c直接输出最小值，否则首先消耗c，c消耗完后取min(a,b)及(a+b)/3的较小者。

`
G
题意：给你一个nXn的棋盘，放置黑白棋子，棋子类似于象棋马的走法，如果能够互相吃到，则称他们为一对，求放置法使得对数最多。
思路：交替放置。

H
题意：有一排木板组成的围栏，木板长度不一，使每一个木板增长1单位要花费b钱，要使得所有相邻木板长度不一，求最小花费。
补思路：一个木板相邻的木板数最多为2个，所以他最多增长2个单位使得和左右都不一样长，那么每一块可以增长的长度为0，1，2.而且每块木板增长的长度与前面木板增长长度有着明显联系–两个增长后长度不能相等。用动态规划求最小的花费。

ll leave[maxn][3];
struct fence
{
    ll len,price;
} fs[maxn];
int main()
{
    ios::sync_with_stdio(false);
    ll t;
    cin>>t;
    while(t--){
    ll n;
    cin>>n;
    for(ll i=0; i<n; i++)
    {
        cin>>fs[i].len>>fs[i].price;
    }
    leave[0][0]=0;
    leave[0][1]=fs[0].price;
    leave[0][2]=fs[0].price*2;
    for(ll i=1; i<n; i++)
    {
        ll df=fs[i].len-fs[i-1].len;
        for(int j=0;j<3;j++)
        {
            leave[i][j]=0x3f3f3f3f3f3f3f3f;
            for(int k=0;k<3;k++)
            {
                if(df+j-k){
                    leave[i][j]=min(leave[i][j],leave[i-1][k]);
                }
            }
            leave[i][j]+=j*fs[i].price;
        }
        //简化前
        /*if(df>0)
        {
            if(df==2)
            {
                leave[i][0]=min(leave[i-1][0],leave[i-1][1]);
                leave[i][1]=min(leave[i-1][0],min(leave[i-1][1],leave[i-1][2]))+fs[i].price;
                leave[i][2]=min(leave[i-1][0],min(leave[i-1][1],leave[i-1][2]))+fs[i].price*2;
            }
            else if(df==1)
            {
                leave[i][0]=min(leave[i-1][0],leave[i-1][2]);
                leave[i][1]=min(leave[i-1][0],leave[i-1][1])+fs[i].price;
                leave[i][2]=min(leave[i-1][0],min(leave[i-1][1],leave[i-1][2]))+fs[i].price*2;
            }
            else
            {
                leave[i][0]=min(leave[i-1][0],min(leave[i-1][1],leave[i-1][2]));
                leave[i][1]=min(leave[i-1][0],min(leave[i-1][1],leave[i-1][2]))+fs[i].price;
                leave[i][2]=min(leave[i-1][0],min(leave[i-1][1],leave[i-1][2]))+fs[i].price*2;
            }
        }
        else
        {
            if(df==0)
            {
                leave[i][0]=min(leave[i-1][1],leave[i-1][2]);
                leave[i][1]=min(leave[i-1][0],leave[i-1][2])+fs[i].price;
                leave[i][2]=min(leave[i-1][0],leave[i-1][1])+fs[i].price*2;
            }
            else if(df==-1)
            {
                leave[i][0]=min(leave[i-1][0],min(leave[i-1][2],leave[i-1][1]));
                leave[i][1]=min(leave[i-1][1],leave[i-1][2])+fs[i].price;
                leave[i][2]=min(leave[i-1][0],leave[i-1][2])+fs[i].price*2;
            }
            else if(df==-2)
            {
                leave[i][0]=min(leave[i-1][0],min(leave[i-1][1],leave[i-1][2]));
                leave[i][1]=min(leave[i-1][0],min(leave[i-1][1],leave[i-1][2]))+fs[i].price;
                leave[i][2]=min(leave[i-1][2],leave[i-1][1])+fs[i].price*2;
            }
            else
            {
                leave[i][0]=min(leave[i-1][0],min(leave[i-1][1],leave[i-1][2]));
                leave[i][1]=min(leave[i-1][0],min(leave[i-1][1],leave[i-1][2]))+fs[i].price;
                leave[i][2]=min(leave[i-1][0],min(leave[i-1][1],leave[i-1][2]))+fs[i].price*2;
            }
        }*/
    }
    cout<<min(leave[n-1][0],min(leave[n-1][1],leave[n-1][2]))<<endl;
}
}

T

本文地址：https://blog.csdn.net/weixin_45931113/article/details/107539197