> 웹 프론트엔드 > HTML 튜토리얼 > Codeforces Round #239 (Div. 2)_Long Path_html/css_WEB-ITnose

Codeforces Round #239 (Div. 2)_Long Path_html/css_WEB-ITnose

WBOY
풀어 주다: 2016-06-24 12:06:09
원래의
918명이 탐색했습니다.

题目链接

  • 题意:
    输入n个值,表示当前点与输入点(关联点)有一条边。初始从1开始,当到达一个点时,点值加一,如果此时值为奇数,那么将走到关联点,否则将到达右边相邻的点
    求到达n+1时,要转移多少次
  • 分析:
    考虑一下第一次到达点P时候的情况,之前的每一个点的值肯定都是偶数(只能从之前的点过来,且只有在值为偶数时才能向右走)。此时因为当前点的值是奇数,所以会到达关联点Q(一定不在当前点的右侧),那么如果想到达下一个点,必须从点Q继续走到点P,而且这个时候的情况和从头走到点Q的情况完全一样(值为偶数和零显然是等价的),也就是得到了子问题
  • 理解:
    此题的状态转移虽然不是一个DAG,但是可以发现转移的时候是有条件的,而且从当前点往回找的时候只能到达之前的状态,所以可以考虑DP
    同样的,DP的关键也在怎么样处理这个“环”
  • const int MAXN = 1100;int ipt[MAXN], dp[MAXN];int main(){//    freopen("in.txt", "r", stdin);    int n;    while (~RI(n))    {        CLR(dp, 0);        FE(i, 1, n) RI(ipt[i]);        FE(i, 1, n)        {            dp[i + 1] = (2 * dp[i] % MOD + MOD + 2 - dp[ipt[i]]) % MOD;        }        WI(dp[n + 1]);    }    return 0;}
    로그인 후 복사


    원천:php.cn
    본 웹사이트의 성명
    본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
    인기 튜토리얼
    더>
    최신 다운로드
    더>
    웹 효과
    웹사이트 소스 코드
    웹사이트 자료
    프론트엔드 템플릿