【强训笔记】day20

NO.1

思路：先判断能对砍几个回合，取最小值，因为回合数是整数，所以可能存在都大于0的情况，再判断一下如果都存活就再对砍一次，直到一家存活或者都死亡。

代码实现：

#include<iostream>

using namespace std;

typedef long long LL;
LL a,h,b,k;

int main()
{
    cin>>a>>h>>b>>k;
    LL n=min(h/b,k/a);
    LL ret=n*(a+b);
        h-=b*n;
        k-=a*n;
    if(h>0&&k>0)
    {
        h-=b;
        k-=a;
        ret+=a+b;
    }
    if(h>0||k>0)
    {
        ret+=10*(h>0?a:b);
    }
    cout<<ret<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

NO.2


思路：动态规划，线性dp。
代码实现：

#include <iostream>
using namespace std;

const int N=2e5+10;
int arr[N];
int dp[N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    int ret=-101;
    for(int i=1;i<=n;i++)
    {
        dp[i]=max(dp[i-1],0)+arr[i];
        ret=max(ret,dp[i]);
    }
    cout<<ret<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

NO.3

思路：先判断特殊情况，字符串内的字符是否全都相等，如果都相等就输出0，再判断是否为回文字符串，是的话只要删除一个就为最大的非回文字符子串，输出n-1，不是的话输出n。

代码实现：

#include<iostream>
#include<string>

using namespace std;

string s;
int n;

int fun()
{
    bool flag=true;
    for(int i=1;i<n;i++)
    {
        if(s[i-1]!=s[i])
        {
            flag=false;
            break;
        }
    }
    if(flag) return 0;
    
    flag=false;
    int left=0,right=n-1;
    while(left<right)
    {
        if(s[left]==s[right])
        {
            left++;
            right--;
        }
        else{
            flag=true;
            break;
        }
    }
    if(flag) return n;
    else return n-1;
    
    
}

int main()
{
    cin>>s;
    n=s.size();
    cout<<fun()<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48