masyarakat Belajar Perpustakaan Alatan Masa lapang
cari
Melayu
Rumah > hujung hadapan web > html tutorial > Codeforces Round #239 (Div. 2)_Long Path_html/css_WEB-ITnose

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

WBOY
Lepaskan： 2016-06-24 12:06:09
asal
916 orang telah melayarinya

题目链接

  • 题意：
    输入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;}
    Salin selepas log masuk


    Label berkaitan：
    Codeforces Round #239 (Div. 2)_Long Path
    sumber：php.cn
    Artikel sebelumnya：EnjoyCSS ? 在线的，先进的 CSS3 代码生成器_html/css_WEB-ITnose Artikel seterusnya：div 居中_html/css_WEB-ITnose
    Kenyataan Laman Web ini
    Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
    Artikel terbaru oleh pengarang
    Isu terkini
    function_exists() tidak boleh menentukan fungsi tersuai Ujian fungsi () {return true;} jika (function_exists ('test')) {echo "test is functio...
    daripada 2024-04-29 11:01:01
    0
    3
    2157
    Bagaimana untuk memaparkan versi mudah alih Google Chrome Hello cikgu, bagaimana saya boleh menukar Google Chrome kepada versi mudah alih?
    daripada 2024-04-23 00:22:19
    0
    11
    2309
    Tetingkap anak mengendalikan tetingkap induk, tetapi output tidak bertindak balas. Dua ayat pertama boleh dilaksanakan, tetapi ayat terakhir tidak boleh dilaksanakan.
    daripada 2024-04-19 15:37:47
    0
    1
    1946
    Tiada output dalam tetingkap induk document.onclick = function(){ window.opener.document.write('Saya adalah output tetingkap ...
    daripada 2024-04-18 23:52:34
    0
    1
    1820
    Di manakah perisian kursus tentang pemetaan minda CSS? Perisian kursus
    daripada 2024-04-16 10:10:18
    0
    0
    1874
    Topik-topik yang berkaitan
    Lagi>
    Cadangan popular
    Tutorial Popular
    Lagi>
    Tutorial berkaitan
    Cadangan popular
    Kursus terkini
    Muat turun terkini
    Lagi>
    kesan web
    Kod sumber laman web
    Bahan laman web
    Templat hujung hadapan