Codeforces 41D Pawn 简单dp

题目链接:点击打开链接

给定n*m 的矩阵 常数k

下面一个n*m的矩阵,每个位置由 0-9的一个整数表示

问:

从最后一行开始向上走到第一行使得路径上的和 % (k+1) == 0

每个格子只能向或走一步

求:最大的路径和

最后一行的哪个位置作为起点

从下到上的路径

思路:

简单dp

#include <cstdio>
#include <algorithm>
#include<iostream>
#include<string.h>
#include <math.h>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
#define N 105
#define inf 10000000
#define ll int
int n,m,k;
int dp[N][N][12];
int px[N][N][12], py[N][N][12], sum[N][N][12];
int mp[N][N];
vector<pair<int,int> >ans;
int main(){
    int i, j, z;
    while(~scanf("%d %d %d",&n,&m,&k)){
            k++;
        memset(sum, -1, sizeof sum);
        memset(px, -1, sizeof px);
        memset(py, -1, sizeof py);
        memset(dp, 0, sizeof dp);
        for(i = 1; i <= n; i++)
            for(j = 1; j <= m; j++)
            scanf("%1d",&mp[i][j]);
        for(i = 1; i <= m; i++)
        dp[n][i][mp[n][i] % k] = 1, sum[n][i][mp[n][i] % k] = mp[n][i];

        for(i = n-1; i ; i--){
            for(j = 1; j <= m; j++) {
                int x = i+1, y = j-1;
                if(y>=1)
                {
                    for(z = 0; z <= k; z++)
                    if(dp[x][y][z] && sum[i][j][(z+mp[i][j])%k] < sum[x][y][z]+mp[i][j])
                    {
                        dp[i][j][(z+mp[i][j])%k] = 1;
                        px[i][j][(z+mp[i][j])%k] = x;
                        py[i][j][(z+mp[i][j])%k] = y;
                        sum[i][j][(z+mp[i][j])%k] = sum[x][y][z]+mp[i][j];
                    }
                }
                y = j+1;
                if(y<=m)
                {
                    for(z = 0; z <= k; z++)
                    if(dp[x][y][z] && sum[i][j][(z+mp[i][j])%k] < sum[x][y][z]+mp[i][j])
                    {
                        dp[i][j][(z+mp[i][j])%k] = 1;
                        px[i][j][(z+mp[i][j])%k] = x;
                        py[i][j][(z+mp[i][j])%k] = y;
                        sum[i][j][(z+mp[i][j])%k] = sum[x][y][z]+mp[i][j];
                    }
                }
            }
        }
        int posx = 1, posy = -1, mod = 0, anssum = -1;
        for(i = 1; i <= m; i++)
            if(dp[1][i][0] && anssum<sum[1][i][0])
                posy = i, anssum = sum[1][i][0];
        if(posy==-1){puts("-1");continue;}
        ans.clear();
        while(posy!=-1) {
            ans.push_back(pair<int,int>(posx, posy));
            int tx = px[posx][posy][mod];
            int ty = py[posx][posy][mod];
            mod = ((mod-mp[posx][posy])%k+k)%k;
            posx = tx, posy = ty;
        }
        cout<<anssum<<endl;

        int x = ans[ans.size()-1].first, y = ans[ans.size()-1].second;
        cout<<y<<endl;
        for(i = ans.size()-2; i >= 0; i--){
            int nowx = ans[i].first, nowy = ans[i].second;
            if(nowy>y)
                printf("R");
            else printf("L");
            x = nowx, y = nowy;
        }
        puts("");
    }
    return 0;
}

Codeforces 41D Pawn 简单dp,布布扣,bubuko.com

时间: 07-17

Codeforces 41D Pawn 简单dp的相关文章

POJ 3250 Bad Hair Day 简单DP 好题

Description Some of Farmer John's N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows' heads. Each cow i has a sp

hdu1207 汉诺塔II 简单dp

本文出自:http://blog.csdn.net/svitter 题意:汉诺塔,多了一根柱子,问你寻找最快的移动次数. dp [ n ] = dp [ n - j ] * 2 + pow( 2, j ) - 1; 就是把j个汉诺塔移到一根上dp[ n - j ],然后就是普通的汉诺塔问题,即2^n - 1次移动, 然后把剩下的移动过去dp [ n - j ]. 注意pow(2, j )可能超出long long int范围.写二的次方的时候也可用移位算法. #include <iostream

POJ1088:滑雪(简单dp)

题目链接:  http://poj.org/problem?id=1088 题目要求: 一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小.求可以滑落的最长长度. 题目解析: 首先要先排一下序,因为只能高度递减才能滑行.之后就很简单了,就是简单DP. 即:要求的滑坡是一条节点递减并依次相邻的最长路径,可以先根据高度将所有的点进行排序,在i点的时候,遍历0~i-1个点(升序排序,i前面的点的高度一定小于等于i),取相邻点间的大的路径长度 代码如下: #include <iostream

hdu 1087 简单dp

思路和2391一样的.. <span style="font-size:24px;">#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; const int inf=(0x7f7f7f7f); int main() { int a; int s[10005]; int w[10005];

CodeForces 18E Flag 2 dp

题目链接:点击打开链接 #include<stdio.h> #include<iostream> #include<string.h> #include<set> #include<vector> #include<map> #include<math.h> #include<queue> #include<string> #include<stdlib.h> #include<a

hdu1087 简单DP

I - 简单dp 例题扩展 Crawling in process... Crawling failed Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Description Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HD

2014 HDU多校弟九场I题 不会DP也能水出来的简单DP题

听了ZWK大大的思路,就立马1A了 思路是这样的: 算最小GPA的时候,首先每个科目分配到69分(不足的话直接输出GPA 2),然后FOR循环下来使REMAIN POINT减少,每个科目的上限加到100即可 算最大GPA的时候,首先每个科目分配到60分,然后FOR循环下来使REMAIN POINT减少,每个科目的上限加到85即可,如果还有REMAIN POINT,就FOR循环下来加到100上限即可 不会DP 阿 QAQ 过段时间得好好看DP了  =  = 于是默默的把这题标记为<水题集> //

CodeForces 19B Checkout Assistant dp

题目链接:点击打开链接 #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <iostream> #include <map> #include <set> #include <math.h> using namespace std; #define inf 115292150460684697

HDU 4826 简单DP

Problem Description 度度熊是一只喜欢探险的熊,一次偶然落进了一个m*n矩阵的迷宫,该迷宫只能从矩阵左上角第一个方格开始走,只有走到右上角的第一个格子才算走出迷宫,每一次只能走一格,且只能向上向下向右走以前没有走过的格子,每一个格子中都有一些金币(或正或负,有可能遇到强盗拦路抢劫,度度熊身上金币可以为负,需要给强盗写欠条),度度熊刚开始时身上金币数为0,问度度熊走出迷宫时候身上最多有多少金币? Input 输入的第一行是一个整数T(T < 200),表示共有T组数据.每组数据的