2020.10.31


小蒜头的美味 http://59.61.214.20:3001/oj/#contest/show/560/2


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
#include<bits/stdc++.h>
using namespace std;

long long f[6005];
long long dp[6005][6005];

int main()
{
    freopen("dilicious.in","r",stdin);
    freopen("dilicious.out","w",stdout);
   
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>f[i];
        dp[i][i]=dp[i+n][i+n]=f[i+n]=f[i];
    }
   
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=2*n;i++)
        {
            int j=i+k-1;
            if(j>2*n) continue;
            if(k%2)
            {
                if(f[i-1]>f[j+1]) dp[i-1][j]=max(dp[i][j],dp[i-1][j]);
                else dp[i][j+1]=max(dp[i][j],dp[i][j+1]);
            }
            else
            {
                dp[i-1][j]=max(dp[i][j]+f[i-1],dp[i-1][j]);
                dp[i][j+1]=max(dp[i][j]+f[j+1],dp[i][j+1]);
            }
        }
    }
   
    long long t=0;
    for(int i=1;i<=n;i++)
    {
        t=max(t,dp[i][i+n-1]);
    }
    cout<<t;
   
    return 0;
}

 


石子排序  http://59.61.214.20:3001/oj/#main/show/1875


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
注:以下只有最大值,且没有考虑环的情况;

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

int f[205];
int dp[205][205];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>f[i];
    }
   
    for(int len=2;len<=n;len++)// len 枚举区间长度
    {
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            dp[i][j]=dp[i][i]+dp[i+1][j];
           
            for(int k=i+1;k<j;k++)
            {
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
           
            for(int k=i;k<=j;k++)
            {
                dp[i][j]+=f[k];
            }
        }
    }
    cout<<dp[1][n];
   
    return 0;
}

// 当区间为 1 时,值为 0

//  i      k      j
//dp[i][j] = max ( dp[i][k] + dp[k+1][j] ) + ∑k=i...j

 

题解就不写了吧,代码看看就ok了,我好累 ˊ( TロT)σ

emmm,晚上要吃一盒奥利奥!  我真是太棒了ヾ(*´▽‘*)ノ

day1

T1:小蒜头的魔法

其实就是判断奇偶数问题

末了

T2:小蒜头翻硬币

1001110011

可以理解为从开头到结尾换了几次数字,最后加个特判判断1在最后时的情况

注意样例会给出全部是0或1的坑

T3:小蒜头的美味

桌上摆着环形的 n 道菜,每道菜有个美味值,你和小蒜头打算把这 n 道菜吃完,首先你会首
先选择一道菜吃掉,然后小蒜头选择,两人轮流;接下来每次选择时,你和小蒜头都只能从
空菜盘区间旁边的两个菜中选择。
可惜小蒜头很傻,每次轮到她时只会从这两个菜中选择美味值高的吃掉。请问你在最优策略
下能吃到的美味值总和是多少。

 

dp dp dp

别问我dp是啥,我布吉岛

T4:小蒜头的祖先

https://www.luogu.com.cn/problem/solution/P5002

传送吧

2020冲刺day1

T1 magic 奇1偶0,超大数据,用字符串。

T2 coin 统计出现的零和一的子段数(最后是0的话就不计入)。

——————水题分界线——————

T3 dilicious

区间DP。

题意:环形的 n 道菜,每道菜有美味值。吃完它们,首先你选择一道菜吃掉,然后对方选择,两人轮流;每次选择时,只能从空菜盘区间旁边的两个菜中选择。每次轮到对方时她只会从这两个菜中选择美味值高的吃掉。求你能吃到最大的的美味值总和。

首先开2*n的数组把环展开。

然后开始DP:f[i][j]表示从第i道菜到第j道菜我能获得的最大美味值。

第一重循环选了l次。

第二重循环i,即从第i道菜开始,所以j=i+l-1;如果j>2*n,数组越界跳过;

从此区间的左右更新状态;如果当前l是偶数,则下一道菜是我吃,于是要比较加哪边的数值更大:

f[i-1][j]=max(f[i-1][j],f[i][j]+a[i-1]); f[i][j+1]=max(f[i][j+1],f[i][j]+a[j+1]);

反之,则下一道菜是对方吃,直接更新,不加当前的a[i]数值:

if(a[i-1]>a[j+1]) f[i-1][j]=max(f[i-1][j],f[i][j]); else f[i][j+1]=max(f[i][j+1],f[i][j]);

最后循环找最大的f[i][i+n-1]。

T4 ancestry

畏惧。待我看懂题解后有缘更新。

想喊声“c”的一天

第一题:小蒜头的魔法

(迷信不好呀,骚年人)

就只有我一个人在这...


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<span class="hljs-preprocessor">#<span class="hljs-keyword">include</span>&lt;bits/stdc++.h&gt;</span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> n,i,o=<span class="hljs-number">1</span>;
<span class="hljs-keyword">int</span> main()
{
    freopen(<span class="hljs-string">"magic.in"</span>,<span class="hljs-string">"r"</span>,stdin);
    freopen(<span class="hljs-string">"magic.out"</span>,<span class="hljs-string">"w"</span>,stdout);
    <span class="hljs-built_in">cin</span>&gt;&gt;n;
    <span class="hljs-keyword">for</span>(i=<span class="hljs-number">1</span>;i&lt;n;i++)
    {
        o=(o^<span class="hljs-number">1</span>);
    }
    <span class="hljs-built_in">cout</span>&lt;&lt;o;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}

第二题:小蒜头翻硬币(无不无聊啊——)

首先统计一下有几段1;

然后if(a[0]=='1')

{

cout<<o*2-1;

}

else

{

cout<<o*2;

}

第三题:小蒜头的美味(蒜头真的美味吗?)

注意注意注意!!!!!!!!!!!是环形!!!!!!!!!!!!!!!!!!!!!!

第四题:小蒜头的祖先

cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc

 

 

 

 

NOIP也有可能是CSP但总之就是复赛前的集训的Day 1

传~送~门~

1st

众所周知,1^1=0,0^1=1,1^1^1=1所以偶数个1输出0,否则输出1

可以说是有手就行,是没有人会WA的题呢,至于czh有没有WA就不知道了呢

第二题

题解是判断1的数量(相邻的只算一个)×2,再特判开头是否是1,不是就+1

而我是先去掉末尾的零再判断1和0的数量(相邻的只算一个)

 

Third

dp[i][j]表示由i到j能有的最大收益

输入再转换成一个环

Fliourancalesthrly

不会

201031集训DAY1

T1小蒜头的魔法

高精度读入

判断最后一位数如果是奇数就输出1

否则就输出0


T2小蒜头翻硬币

计算ans=1段和0段的总数

判断最后一段如果是0

那么ans-1


T3小蒜头的美味

是一道区间dp

定义L是区间长度则j=i+L-1

注意这是一个环 记得a[i+n]=a[i];
还要判断if(j>2*n) continue;
if(l%2==1){
if(a[i-1]>a[j+1]){
dp[i-1][j]=max(dp[i-1][j],dp[i][j]);
}
else
dp[i][j+1]=max(dp[i][j+1],dp[i][j]);}
else{
dp[i-1][j]=max(dp[i-1][j],dp[i][j]+a[i-1]);
dp[i][j+1]=max(dp[i][j+1],dp[i][j]+a[j+1]);
}

T4小蒜头的祖先

🙂

幸灾乐祸的蒟蒻

T1

肯定直接找规律判断奇偶了啦每个人都懂的对不对

T2

从后往前把硬币翻过来,反着模拟就好

直接数这排硬币段数即可

要特判o

T3

主要思路是模拟拿1,2,3......n道菜的情况,再分小蒜头和我拿菜的情况(奇偶),再把区间内最大值表示出来

dp一定要调试!!不然怎么死的真的不知道!!

T4

2020.10.31

T1.小蒜头的魔法

判断奇偶。

T2.小蒜头翻硬币

 

从后往前,碰到1开始,之后每次数字不同就ans++;

T3.小蒜头的美味

常规的第3题运用区间DP。

先枚举没一个动作,然后利用区间DP枚举最左点不断更新最大值。

发现被吃掉的菜肴一直都是相连的一段区间[L,R]
所以我们考虑一个区间 DP表示从目前被吃掉的区间是 (i,j)的情况下你的最大收益,当前区间长度为奇数时,则下一位是小蒜头吃,小蒜头则选择左右中最大的,若是小蒜头吃dp[i][j]不变,反之则更新

因为这是个环,所以

T4.小蒜头的祖先