지역 사회 배우다 도구 라이브러리 여가
찾다
한국어
집 > 웹 프론트엔드 > 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
원래의
916명이 탐색했습니다.

题目链接

  • 题意：
    输入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;}
    로그인 후 복사


    관련 라벨：
    Codeforces Round #239 (Div. 2)_Long Path
    원천：php.cn
    이전 기사：EnjoyCSS ? 在线的，先进的 CSS3 代码生成器_html/css_WEB-ITnose 다음 기사：div 居中_html/css_WEB-ITnose
    본 웹사이트의 성명
    본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
    저자별 최신 기사
    최신 이슈
    function_exists()는 사용자 정의 함수를 결정할 수 없습니다. 기능 테스트() {                                                                                ...
    에서 2024-04-29 11:01:01
    0
    3
    2157
    Chrome 모바일 버전을 표시하는 방법 안녕하세요 선생님, Chrome을 모바일 버전으로 어떻게 변경하나요?
    에서 2024-04-23 00:22:19
    0
    11
    2309
    자식 창이 부모 창을 작동하지만 출력이 응답하지 않습니다. 처음 두 문장은 실행 가능하지만 마지막 문장은 구현할 수 없습니다.
    에서 2024-04-19 15:37:47
    0
    1
    1946
    상위 창에 출력이 없습니다. document.onclick = function(){ window.opener.document.write('나는 자식 창의 출력입니다.');
    에서 2024-04-18 23:52:34
    0
    1
    1820
    CSS 마인드맵 코스웨어는 어디에 있나요? 코스웨어
    에서 2024-04-16 10:10:18
    0
    0
    1874
    관련 주제
    더>
    인기 추천
    인기 튜토리얼
    더>
    관련 튜토리얼
    인기 추천
    최신 강좌
    최신 다운로드
    더>
    웹 효과
    웹사이트 소스 코드
    웹사이트 자료
    프론트엔드 템플릿