代码之家 › 专栏 › 技术社区 › Srinivasan A

动态编程:(不吃冰淇淋的最短天数)

dynamic-programming data-structures python-3.x arrays python

Srinivasan A · 技术社区 · 1 周前

不吃冰淇淋的最短天数

拉姆决定连续N天吃冰淇淋。每天,冰淇淋店都可以有巧克力味或芒果味,也可以两者兼而有之,也可以不吃。冰淇淋口味的可用性表示为1代表巧克力,2代表芒果,3代表两者,0代表无。拉姆不喜欢连续两天吃同样的冰淇淋。找出拉姆不吃冰淇淋的最少天数。

边界条件: 1<=N<=100000

输入格式:

第一行包含N的值。第二行包含N个用空格分隔的整数。

输出格式: 第一行包含Ram不吃冰淇淋的最低天数。

示例输入/输出1:

输入
5.
1 2 1 0 2

输出
1.

示例输入/输出2:

输入
8.
2 1 1 1 3 3 3 2

输出
2.

解释
第一天,公羊吃芒果味的食物。
第二天,公羊吃巧克力味的食物。
第三天,他可以吃巧克力,但不能连续两天吃同样的味道。所以他什么都不吃。第4天,公羊吃巧克力味的食物。
第5天,拉姆吃芒果味。
第六天,拉姆吃巧克力口味的食物。
第7天,拉姆吃芒果味。
第八天,拉姆什么都不吃。

隐藏案例:

I/P:

3001

1 1 0 3 1 3 2 0 3 0 1 2 3 0 2 1 2 2 0 3 3 2 0 3 1 1 2 3 0 1 0 1 3 1 1 3 0 0 3 3 0 0 1 2 0 3 3 3 1 2 1 3 1 1 0 3 0 1 0 2 2 0 3 0 2 2 1 1 2 0 3 1 1 1 0 0 1 2 1 2 2 1 0 2 3 0 2 2 3 1 0 3 2 2 0 1 3 2 0 2 3 3 1 2 2 0 1 2 2 2 2 0 0 2 1 0 3 3 1 3 1 3 0 3 2 3 1 3 3 0 0 1 3 2 3 1 0 3 1 0 2 0 2 3 0 1 3 0 1 3 0 3 3 0 3 2 2 1 1 3 1 0 3 0 0 1 2 2 3 2 1 1 2 0 1 3 1 2 0 1 1 2 1 2 0 2 0 0 3 0 0 1 0 1 3 2 3 0 1 3 1 3 1 2 2 3 3 1 3 3 0 0 3 2 3 0 0 2 3 2 0 0 0 2 2 3 2 0 0 1 2 2 0 0 1 1 2 3 3 0 3 2 3 2 3 2 1 0 3 1 3 1 0 0 1 2 1 3 0 0 0 0 1 0 2 1 0 2 0 3 3 3 0 2 0 1 1 3 1 2 2 2 0 0 2 2 1 1 2 3 0 2 0 0 3 1 1 1 2 2 3 2 0 1 2 2 1 0 1 3 1 1 1 2 1 2 3 2 2 3 0 1 1 2 3 1 2 0 3 1 0 0 3 0 3 1 3 1 2 3 0 2 3 0 1 3 0 2 0 1 0 3 1 1 0 3 1 1 0 0 1 0 2 0 0 3 0 1 0 2 3 1 0 0 2 0 1 1 0 0 3 0 0 1 2 0 0 1 2 2 0 1 3 3 0 0 2 1 3 1 0 0 2 3 1 2 1 0 3 3 0 1 1 1 2 3 0 3 2 0 2 0 3 0 2 3 0 0 0 2 2 2 3 2 0 3 1 2 1 2 2 3 1 2 2 2 3 2 3 0 1 0 2 3 0 0 1 0 2 0 1 2 2 1 2 3 0 0 3 3 0 1 1 2 0 2 2 3 3 2 2 0 3 3 2 1 0 3 3 0 3 1 1 2 0 2 3 0 0 1 3 1 0 3 2 0 1 2 1 2 3 3 1 0 1 1 1 0 0 1 0 1 2 2 3 1 2 0 2 0 0 1 2 1 3 3 2 3 2 0 2 1 3 0 0 2 2 3 0 2 0 3 0 1 0 0 2 3 2 3 2 2 2 2 3 0 1 3 2 3 1 0 0 0 3 3 2 3 2 2 2 0 1 1 3 3 3 0 2 0 2 0 0 1 0 0 0 3 3 0 1 1 1 3 3 3 3 3 3 2 2 0 0 2 3 2 3 3 1 1 3 0 2 1 1 0 0 0 2 1 1 3 2 1 3 1 3 3 1 1 0 3 0 3 1 2 2 3 0 0 1 1 2 0 2 0 3 3 1 1 3 1 1 0 0 1 2 3 1 3 1 2 1 1 1 0 0 2 0 2 0 2 2 1 0 2 3 3 1 2 1 3 3 1 1 3 2 3 2 1 3 3 2 3 2 1 3 0 2 3 2 1 2 3 0 0 3 3 2 0 0 1 2 1 0 3 3 2 2 3 0 3 3 0 0 1 2 2 0 0 3 2 2 2 2 3 0 1 2 3 0 3 1 2 0 0 1 1 3 1 0 2 0 3 2 2 2 0 1 2 2 2 1 3 3 3 1 2 3 3 3 3 3 3 3 3 1 2 2 1 2 2 3 3 3 0 3 1 1 0 2 1 0 1 2 1 2 0 0 3 0 0 3 1 2 3 0 2 0 2 1 0 0 0 2 3 0 3 2 3 0 2 2 2 2 0 0 0 2 1 0 2 2 1 1 3 0 3 1 1 2 2 1 3 2 1 1 3 3 1 0 3 3 2 1 3 2 2 2 1 3 0 3 3 3 0 2 0 2 3 1 2 1 2 3 1 3 1 1 3 2 3 0 3 3 1 0 1 3 0 3 2 3 1 3 0 1 2 0 1 3 1 1 1 3 0 0 2 3 3 1 2 1 3 1 3 0 0 0 0 3 0 0 2 2 0 1 3 3 2 0 2 1 0 0 2 3 0 3 1 1 2 0 1 2 0 0 1 1 0 1 0 1 2 2 2 0 1 0 3 3 3 2 3 1 1 2 1 3 1 1 0 2 2 0 2 3 3 3 0 3 1 0 2 2 2 3 3 3 1 3 1 1 3 2 2 3 2 0 1 2 1 3 1 3 0 1 3 2 2 2 1 2 3 2 1 3 1 0 3 0 3 1 2 2 2 2 2 3 1 0 0 1 2 2 1 0 1 0 3 0 2 2 1 2 0 2 3 1 3 0 1 0 2 0 1 0 2 3 0 1 0 1 1 0 3 0 3 0 0 2 0 1 2 3 3 1 0 2 0 1 2 1 2 2 2 1 3 2 1 0 3 3 2 0 1 1 1 0 0 2 0 3 2 0 0 1 3 1 2 1 2 1 2 2 0 1 2 2 1 1 0 2 2 2 2 3 3 0 3 1 2 3 1 0 3 2 0 2 1 3 0 0 2 2 2 0 3 2 2 1 2 1 0 0 0 0 0 0 1 3 2 2 0 3 0 2 3 0 2 1 2 1 1 3 2 0 3 0 1 1 2 0 3 3 0 1 1 0 3 0 0 3 1 3 3 3 0 0 0 3 3 1 1 2 2 2 2 2 0 0 0 3 2 1 1 2 0 2 0 2 3 0 3 1 1 1 0 1 3 2 0 0 1 2 3 2 3 2 0 2 1 0 2 2 2 0 1 3 1 0 0 2 2 1 2 0 0 3 0 1 1 0 3 0 0 2 0 2 3 1 3 1 0 0 0 3 1 2 2 0 3 2 2 1 1 1 0 0 2 2 0 3 2 3 2 2 3 0 1 0 3 0 0 1 2 3 2 3 1 1 1 1 1 0 2 1 0 0 1 3 0 0 3 2 3 0 3 0 3 1 2 2 0 0 1 3 3 1 2 1 2 0 1 3 2 3 3 3 0 0 0 0 3 2 1 0 1 0 3 3 0 0 2 2 2 1 3 1 1 1 1 2 2 0 2 3 2 2 3 0 0 1 3 0 2 2 0 1 1 0 3 0 2 2 1 0 2 1 0 0 2 0 0 0 3 2 0 0 2 1 1 3 3 0 3 3 0 3 0 3 0 0 3 3 1 2 3 3 0 0 1 0 2 2 0 1 2 3 3 1 2 2 1 2 2 3 2 0 0 2 3 1 0 0 1 1 3 0 0 2 1 3 3 3 1 0 2 3 3 3 0 2 0 0 3 3 2 2 1 3 2 3 0 1 1 2 2 0 3 3 2 2 1 3 3 2 3 0 2 0 3 1 1 3 2 3 3 2 1 2 3 0 0 0 0 3 3 1 2 1 2 2 0 2 1 0 0 2 3 3 2 0 1 2 1 2 3 1 2 2 3 1 3 0 1 1 3 1 3 3 0 1 0 2 1 0 1 0 2 1 2 2 2 2 3 0 2 1 0 2 1 0 3 0 0 3 0 0 0 1 1 3 1 2 2 3 3 1 2 0 1 2 0 2 3 0 0 0 2 1 3 2 0 2 3 0 2 3 1 2 1 1 3 3 1 2 3 2 1 0 2 1 3 3 3 2 2 1 3 3 0 0 3 2 1 2 0 2 2 0 0 3 3 1 1 2 1 0 0 1 0 3 1 0 1 3 1 0 2 0 2 2 1 1 1 2 1 1 2 3 1 1 3 1 1 3 1 2 0 3 0 0 1 0 3 1 1 1 3 2 1 2 1 3 1 0 1 0 2 2 0 2 1 0 0 2 1 0 0 1 0 2 2 2 1 0 0 2 0 0 3 3 2 0 2 3 2 3 0 2 2 1 0 1 3 1 3 1 0 0 2 0 0 0 2 0 0 3 2 2 0 1 1 3 0 0 2 2 2 3 3 3 2 2 0 2 0 2 3 1 3 3 0 2 3 3 3 0 3 1 1 2 3 0 3 1 0 2 1 0 2 1 3 2 2 2 0 2 2 3 1 0 0 0 2 1 3 1 0 1 3 2 2 0 0 1 2 1 2 3 3 0 2 1 0 3 0 2 1 3 1 2 2 2 0 3 2 3 3 1 3 3 0 2 2 1 2 3 0 1 0 1 1 1 2 1 1 0 2 3 1 2 3 1 2 1 2 0 1 0 1 2 2 0 2 0 2 2 1 3 1 1 1 1 3 1 1 1 2 3 1 2 1 2 1 2 1 2 1 1 1 2 0 1 2 0 3 2 1 0 1 1 0 1 0 3 0 0 1 0 1 0 0 2 0 2 3 0 0 2 2 0 0 2 1 0 1 2 3 1 2 2 3 0 0 1 3 0 2 2 1 2 1 2 0 3 3 0 1 2 0 2 3 0 3 1 1 2 0 0 1 1 0 1 1 2 2 1 0 3 0 0 0 0 1 2 1 0 2 2 0 0 1 3 3 1 1 3 1 3 3 1 1 2 2 3 0 1 1 2 0 1 2 3 3 0 2 3 2 0 3 1 2 1 0 3 0 2 2 2 3 0 2 3 0 2 2 2 0 2 1 3 1 3 3 1 0 3 1 0 0 2 0 3 3 0 3 1 3 2 1 2 2 3 0 0 3 2 0 1 1 2 2 0 0 2 2 1 3 1 1 0 0 3 1 3 2 3 2 1 2 2 3 1 0 2 1 3 1 0 3 3 2 2 0 1 2 1 0 0 2 1 2 2 1 1 0 0 1 1 2 1 1 0 2 2 2 3 3 2 2 1 1 1 0 3 3 1 2 3 2 3 1 0 1 2 2 1 2 3 1 2 2 0 3 2 3 0 3 1 2 3 1 2 3 2 0 3 2 0 1 3 0 2 0 2 3 3 2 1 1 3 3 3 1 2 2 2 3 1 1 0 1 2 2 2 3 1 0 2 0 0 1 1 1 3 3 2 1 3 2 1 2 2 3 1 0 2 2 0 3 1 2 3 3 3 2 1 0 2 0 1 2 0 1 3 1 3 1 0 2 0 2 3 2 3 1 3 2 1 2 0 0 1 2 3 3 0 1 3 2 3 2 3 3 3 2 0 3 1 1 2 1 0 0 3 1 0 2 1 1 1 0 2 0 2 0 2 3 3 3 3 3 0 1 2 2 1 1 0 1 0 1 1 3 2 2 3 2 1 3 1 3 0 1 2 3 3 1 1 1 0 2 3 3 0 2 0 0 0 0 3 3 2 2 3 0 3 1 1 1 3 2 3 2 1 3 0 2 0 3 0 0 3 2 0 2 1 2 0 2 0 0 0 2 0 0 1 1 1 2 1 3 0 2 3 2 2 3 3 1 3 1 2 2 1 3 0 0 2 0 0 3 2 1 1 3 2 2 2 1 3 0 3 0 0 1 2 0 2 0 0 3 1 1 2 1 3 0 2 3 2 0 2 2 1 1 2 3 3 3 0 0 3 3 0 3 3 1 3 1 2 1 2 1 0 1 0 0 0 1 2 1 2 1 0 1 1 3 0 1 0 3 3 1 0 3 3 2 2 1 2 2 0 1 3 2 1 3 1 3 3 3 2 3 0 3 1 1 0 3 0 0 1 0 2 3 2 2 1 1 3 3 3 2 0 1 2 3 3 2 3 3 3 3 3 3 2 1 2 2 0 0 0 1 2 1 0 1 2 0 1 2 2 2 3 0 2 1 2 1 2 3 1 0 3 2 1 1 3 3 3 1 1 2 3 3 0 3 0 2 2 1 1 2 1 0 0 3 1 3 0 3 1 1 3 3 0 2 1 2 0 0 2 2 3 0 0 2 2 0 1 3 1 3 2 3 1 3 1 0 2 1 0 1 3 1 1 3 3 2 3 0 0 1 3 3 2 1 3 1 1 1 1 0 1 2 2 3 2 3 1 2 1 0 3 1 3 0 1 0 2 3 1 2 2 1 2 1 3 2 3 0 3 3 1 0 1 1 1 3 1 3 1 3 2 0 2 0 1 3 0 2 3 2 2 0 0 2 1 3 0 2 1 1 3 1 1 1 2 2 2 1 2 0 1 0 2 3 2 3 2 0 1 2 0 1 3 1 3 3 2 0 3 0 2 2 1 1 0 2 3 0 3 1 0 3 0 3 0 1 3 1 3 3 0 0 2 1 0 1 1 2 2 0 0 3 1 1 2 3 2 2 2 2 3 3 0 2 0 3 3 2 1 2 1 2 3 0 0 3 1 3 3 1 1 2 0 2 2 3 0 2 3 0 0 1 0 2 1 2 2 0 1 3 0 0 0 1 3 0 1 3 0 2 2 2 1 3 1 1 3 2 0 2 0 1 3 2 0 0 0 1 1 1 0 3 3 1 3 3 2 0 2 1 3 0 3 2 1 1 1 2 2 0 1 3 3 2 0 1 3 0 2 1 2 1 2 2 1 1 2 3 1 1 3 3 3 0 3 0 0 2 2 2 0 1 0 3 1 3 3 2 0 2 0 0 1 3 1 0 3 2 1 0 2 3 1 0 1 1 0 2 2 0 2 3 3 3 3 0 0 3 3 2 2 2 1 3 3 3 3 3 3 0 2 1 2 3 0 2 2 0 3 0 3 2 1 0 2 1 0 0 2 3 1 3 3 2 3 1 2 1 2 3 0 0 2 2 3 0 1 2 3 2 3 0 0 3 1 1 1 0 2 3 2 0 2 2 2 0 2 3 0 1 0 2 1 0

预期输出:

1114

您的程序输出:

1126

5个私有(隐藏)测试用例失败。

0通过 5失败

代码:

n=int(input())
ar=list(map(int, input().split()))
dp=n*[-1]
c=0
prev, dp[0]=ar[0],ar[0]
for i in range(1,n-1):
    if ar[i]==prev:
    dp[i]=0
    prev=dp[i]
    continue
    if ar[i]==0:
    dp[i]=0
    prev=0
    continue
    if ar[i]==3 and prev==0:
    if ar[i+1]==1:
       dp[i]=2
    elif ar[i+1]==2:
       dp[i]=1
    prev=dp[i]
    continue
    if ar[i]==3 and prev==1:
    dp[i]=2
    prev=dp[i]
    elif ar[i]==3 and prev=2:
    dp[i]=1
    prev=dp[i]
    else:
    dp[i]=ar[i]
    prev=dp[i]
if prev==ar[n-1]:
    dp[n-1]=0
else:
    dp[n-1]=ar[n-1]
for i in dp:
    if i==0:
    c+=1
print(c)

对不起,伙计们,我是动态编程的新手,我不知道出了什么问题。。。。。

1 回复 | 直到 1 周前

Frank Yellin 1 周前

这实际上与动态编程无关。你只需在数组中迭代,记录你跳过了多少天,以及当天可以吃什么。让我们使用值1、2和3来指示你可以吃什么,就像它用来跟踪商店供应什么一样。

allowed = 3
skipped = 0
for value in array_of_store_values:
    if value == 0:
        # Nothing there.  I have to skip.  Tomorrow I'll eat anything
        skipped += 1 
        allowed = 3 
    elif value in (1, 2):  # restaurant only has one flavor
        if allowed in (value, 3): 
            # I can eat the restaurant's flavor.  Tomorrow the other
            allowed = 3 - value
        else:
            # No ice cream today
            skipped += 1
            allowed = 3
    else:
        # The restaurant has both.  If I'm allowed to eat anything, then
        # I can delay my decision on what to eat today until I found out what
        # they have tomorrow.  But if I'm only allowed to eat one flavor, 
        # eat it, and tomorrow I have to eat the other.
        if allowed != 3:
            allowed = 3 - allowed

print(skipped)