DP基礎練習1

11138 ワード
問題:
階段はM級で、最初は1級で、毎回1級か2級しか越えられない場合は、M級に上がるには、何種類の歩き方がありますか?
Input
入力データは、まず、試験例の個数を表す整数N、次いでN行のデータを含み、各行には階段の段数を表す整数M(1<=M<=40)が含まれる.
Output
各テストインスタンスについて、異なるパスの数を出力します.
Sample Input 
2
2
3

Sample Output 
1
2

考え方:
dp[1]=0;
dp[2]=1;
dp[3]=2;
移行方程式:dp[M]=dp[M-1]+dp[M-2]
コード:
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=200;
int dp[50];
void solve()
{
    dp[1]=0;
    dp[2]=1;
    dp[3]=2;
    for(int i=4;i<=40;i+=1){
        dp[i]=dp[i-1]+dp[i-2];
    }
}
int main()
{
    solve();
    //printf("%d
",dp[40]);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        printf("%d
",dp[n]);
    }
    return 0;
}

 
問題:
ある国は敵国のミサイル襲撃を防ぐために、ミサイル迎撃システムを発展させた.しかし、このミサイル迎撃システムには、最初の砲弾は任意の高さに達することができるが、その後、各砲弾は前の砲弾の高さを超えてはならないという欠陥がある.ある日、レーダーが敵国のミサイル襲撃を捉えた.このシステムはまだ試用段階にあるため、1セットのシステムしかないため、すべてのミサイルを遮断できない可能性がある.どうしようかな?もっとシステムを作ってください.君の言うことは簡単だが,コストは?コストは大きな問題ですね.だから私はここに助けを求めに来ました.少なくとも何セットのブロックシステムが必要か計算してください. 
Input
複数組のデータを入力.各グループのデータには、ミサイルの総個数(正の整数)、ミサイルが飛来する高さ(レーダーが与える高さデータは30000以下の正の整数で、スペースで区切られている)が含まれています.
Output
各組のデータ出力に対応してすべてのミサイルを遮断するには、少なくとも何セットのこのようなミサイル遮断システムが配備される必要があるか. 
Sample Input 
8 389 207 155 300 299 170 158 65

Sample Output 
2

構想:i発目のミサイルが飛来した場合、既存のシステムがそれを遮断できるかどうかを見る.あるシステムが遮断できると、そのシステムが最も遮断できるミサイルの高さ(dp[index]=height[i])を更新し、できない場合は、現在最も遮断できるミサイルの高さがi番目のミサイルの高さであるシステムを複数配備する.
コード:
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e4+5;
int dp[N],x[N],y;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;++i){
            scanf("%d",&x[i]);
        }
        dp[0]=x[1];
        int Count=1;
        for(int i=1;i<=n;++i){
            for(y=0;y=Count)
            {
                dp[y]=x[i];
                Count+=1;
            }
        }
        printf("%d
",Count);
    }
    return 0;
}

 
問題:
DPアルゴリズムについて述べるとき、古典的な例は数塔問題であり、以下に示す数塔があり、最上階から下層まで行くことが要求され、一歩ごとに隣接するノードまでしか歩けない場合、通過するノードの数の和は最大でいくらですか.もう教えてあげました.これはDPのテーマです.ACできますか.
Input
入力データは、まず、試験例の個数を表す整数Cを含み、各試験例の最初の行は整数N(1<=N<=100)であり、数塔の高さを表す.次に、i行目にi個の整数があり、すべての整数は区間[0,99]内にある. 
Output
各テストインスタンスについて、出力可能な最大和は、各インスタンスの出力が1行を占める. 
Sample Input 
1
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

Sample Output 
30

構想:実は木の塔は1本の木で、各層のノード番号に対して、順番は上から下まで、左から右までです.ツリーのルートからリーフノードまでのすべてのノード価値と最大のパスを探し、各親ノードの最適値(max{(cur[father]+dp[child 1],cur[father]+dp[child 2])を下から上へ更新できます.
コード:
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e4+5;
int cur[N],dp[N];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        int node=0;
        for(int i=1;i<=n;i+=1){
            for(int y=1;y<=i;y+=1){
                int x;
                scanf("%d",&x);
                node+=1;
                cur[node]=x;
            }
        }
        memset(dp,0,sizeof(dp));
        for(int i=node;i>node-n;i--)
            dp[i]=cur[i];
        node-=n;
        for(int i=n-1;i>=1;i--){
            for(int y=1;y<=i;y+=1){
                dp[node]=max(dp[node+i]+cur[node],dp[node+i+1]+cur[node]);
                node--;
            }
        }
        printf("%d
",dp[1]);
    }
    return 0;
}

 
問題:
A frog lives on the axis Ox and needs to reach home which is in the point n. She starts from the point 1. The frog can jump to the right at a distance not more than d. So, after she jumped from the point x she can reach the point x + a, where a is an integer from 1 to d.
For each point from 1 to n is known if there is a lily flower in it. The frog can jump only in points with a lilies. Guaranteed that there are lilies in the points 1and n.
Determine the minimal number of jumps that the frog needs to reach home which is in the point n from the point 1. Consider that initially the frog is in the point 1. If the frog can not reach home, print -1.
Input
The first line contains two integers n and d (2 ≤ n ≤ 100, 1 ≤ d ≤ n - 1) — the point, which the frog wants to reach, and the maximal length of the frog jump.
The second line contains a string s of length n, consisting of zeros and ones. If a character of the string s equals to zero, then in the corresponding point there is no lily flower. In the other case, in the corresponding point there is a lily flower. Guaranteed that the first and the last characters of the string s equal to one.
Output
If the frog can not reach the home, print -1.
In the other case, print the minimal number of jumps that the frog needs to reach the home which is in the point n from the point 1.
Examples
Input 
8 4
10010101

Output 
2

Input 
4 2
1001

Output 
-1

Input 
8 4
11100101

Output 
3

Input 
12 3
101111100101

Output 
4

Note
In the first example the from can reach home in two jumps: the first jump from the point 1 to the point 4 (the length of the jump is three), and the second jump from the point 4 to the point 8 (the length of the jump is four).
In the second example the frog can not reach home, because to make it she need to jump on a distance three, but the maximum length of her jump equals to two.
标题:1次元の座標軸上で、カエルは位置1から出発し、位置nに到達する.ステップごとに最大d単位歩くことができて、位置nに必要な最低ステップ数はいくらですか?
位置kに到達するには、k位置の対応文字が「1」であることが制限されている.
考え方:
位置x->yから必要な最小ステップ数を更新し続ける
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e4+5;
int x[N],dp[N];
char str[N];
int main()
{
    int n,d;
    while(~scanf("%d%d",&n,&d))
    {
        scanf("%s",str+1);
        if(str[1]=='0')
        {
            printf("-1
");
            continue;
        }
        for(int i=1;i<=n;i+=1){
            dp[i]=N;
        }
        dp[1]=0;
        for(int p=1;pn) break;
                if(str[s+p]=='1')
                    dp[p+s]=min(dp[p+s],dp[p]+1);
            }
            //printf("%d
",dp[p]);
        }
        if(dp[n]==N)
            printf("-1
");
        else
            printf("%d
",dp[n]);
    }
    return 0;
}

 
問題:
In Python, code blocks don't have explicit begin/end or curly braces to mark beginning and end of the block. Instead, code blocks are defined by indentation.
We will consider an extremely simplified subset of Python with only two types of statements.
Simple statements are written in a single line, one per line. An example of a simple statement is assignment.
For statements are compound statements: they contain one or several other statements. For statement consists of a header written in a separate line which starts with "for"prefix, and loop body. Loop body is a block of statements indented one level further than the header of the loop. Loop body can contain both types of statements. Loop body can't be empty.
You are given a sequence of statements without indentation. Find the number of ways in which the statements can be indented to form a valid Python program.
Input
The first line contains a single integer N (1 ≤ N ≤ 5000) — the number of commands in the program. N lines of the program follow, each line describing a single command. Each command is either "f"(denoting "for statement") or "s"("simple statement"). It is guaranteed that the last line is a simple statement.
Output
Output one line containing an integer - the number of ways the given sequence of statements can be indented modulo 109 + 7.
Examples
Input 
4
s
f
f
s

Output 
1

Input 
4
f
s
f
s

Output 
2

Note
In the first test case, there is only one way to indent the program: the second for statement must be part of the body of the first one. 
simple statement
for statement
    for statement
        simple statement

In the second test case, there are two ways to indent the program: the second for statement can either be part of the first one's body or a separate statement following the first one. 
for statement
    simple statement
    for statement
        simple statement

or 
for statement
    simple statement
for statement
    simple statement

題意:pythonには、n個のforループや陳述文が与えられ、’f’には文が必要である.pythonインデント方式で合法的なプログラムに組み合わせることが要求され、最後の行は必ず陳述される.何種類の可能性のある案があるかを聞く.
考え方:
dp[i][j]意味:i行目のjインデントのシナリオ数
i行目の文が'f'である場合、i+1行目の文は必ずインデントされます.インデントスキームdp[i+1][j+1]=dp[i][j];
i行目の文が's'である場合、i+1行目の文は一定<=i行目のインデントにインデントされる.インデントスキームdp[i+1][j]=Σdp[i][k](j<=k<=n-1)
コード:
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=5e3+5;
const ll Mod=1e9+7;
ll dp[N][N];
int main()
{
    int n;
    scanf("%d",&n);
    memset(dp,0,sizeof(dp));
    dp[1][0]=1;
    char c;
    ll s;
    for(int i=1;i>c;
        if(c=='f')
        {
            for(int j=0;j=0;--j){
                s=(s+dp[i][j])%Mod;
                dp[i+1][j]=s;
            }
        }
    }
    cin>>c;
    s=0;
    for(int j=0;j

シリアルポートがオフラインかどうかを検出する考え方
bool型戻り値関数、return文を書かなかったときに何を返しますか?