跳至正文

USACO 1.1.4 Broken Necklace

  • OI路程

  这一题以前我就有疑问,为什么代码一定是:

a = b – w;
b = w + 1;
  而不能是:
a = b;
b = 1;
  今天终于是把它给想通了,理由如下:
  这里之所以要写成a = b – w, b = w + 1 而不是a = b, b = 1 的原因我终于是找到了.原因如下:
  假设: 此时 b = 2, w = 1 则执行
  a = b, b = 1 之后的
  1.a = 2, b = 1
  而下一次就又进入这里,
  2.a = 1, b = 1
  但是不是有更好的分配方法么:

  1.a = b – w = 1, b = w + 1 = 2
  虽然和上面的和相同都是3, 但是对后面结果的影响不同了:
  2.a = b – w = 2 – 0 = 2, b = 1
  不久比上面的要好上1 ?  
  代码附上:
/
LANG:
C

ID: logoo2
PROG:
beads

/
#include
<stdio.h>
#include <string.h>

char str[10001];

int main(void)
{
        int a = 0, b = 0, w = 0;
        char ch = ‘w’;
        int i,
n;
        int ans = 0;
        freopen("beads.in", "r", stdin);
        freopen("beads.out", "w", stdout);
        scanf("%d\n", &n);
        scanf("%s",
str);
        for(i = 0; i < n; i++){
                str[i + n] =
str[i];
        }
        str[i + n] = ‘\0’;
        for(i =
0; i < 2  n &&
ans < n; i++){
                if(str[i]
== ‘w’){
                        b++,
w++;
                }else if(str[i] != ch){
                        if(a + b >
ans){
                                ans = a +
b;
                        }
                        /

                          这里之所以要写成a = b – w, b = w + 1
而不是

                        a = b, b = 1
的原因我终于是找到了.原因如下:

                        假设: 此时 b
= 2, w = 1 则执行

                        a = b, b =
1 之后的

                        1.a = 2, b =
1

                        而下一次就又进入这里,
                        2.a = 1, b = 1
                        但是不是有更好的分配方法么:

                        1.a = b – w = 1, b = w + 1 =
2

                        虽然和上面的和相同都是3,
但是对后面结果的影响不同了:

                        2.a = b – w
= 2 – 0 = 2, b = 1

                        不久比上面的要好上1 ?  
                        */
                        a = b –
w;
                        b = w + 1;
                        w = 0;
                        ch =
str[i];
                }else{
                        b++, w = 0;
                }
        }
        if(a + b > ans){
                ans = a +
b;
        }
        if(ans >
n){
                ans = n;
        }
        printf("%d\n", ans);
        return 0;
}

发表评论

您的电子邮箱地址不会被公开。