# Codeforces 41D Pawn 简单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

## 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

## 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

## HDU 4826 简单DP

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