首页 > > 程序设计 > C/C++ >

Gym 100703G---Game of numbers（DP）

2018-06-17 23:45:53来源：未知阅读 ()

题目链接

http://vjudge.net/contest/132391#problem/G

Description

standard input/output
Statements

— It' s a good game, — Princess said pensively. It was clear that she was thinking about something else.

— They like to play various games here in Castles Valley. And they invent ones themselves. Say, my friend Knight played with a princess a game some time ago, — Dragon thought it was a good idea o tell Princess about another game, if, perhaps, previous game was seemed no interesting for her.

Princess A. offered Knight to play a game of numbers. She puts down the number zero on a sheet of paper. Let us call this number acurrent result.

Further steps of princess A. and Knight are described below. She calls any positive integer and Knight says what she must do with this number: to add it to the current result or subtract it from the current result.

Princess A. performs the action and calculates a new value. This value becomes the new current result.

Princess A. wants that current result to be not less than zero and not greater than k at any time. The game finishes when an action makes the result out of the range or when a sequence of n numbers, which princess A. conceived, exhausts.

Knight managed to learn the sequence of n numbers that princess A. guessed, and now he wants the game to last as long as possible.

Your task is to compute maximum possible number of actions which Knight is able to perform during the game.

Input

The first line contains integers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 1000) — the size of sequence which princess A. conceived and an upper bound for a current result which must not be exceeded.

The second line contains n integers c₁, c₂, ..., c_n (1 ≤ c_j ≤ k) — the sequence which princess A. conceived.

Output

In the first line print integer d — maximum possible number of actions, which Knight is able to perform during the game.

Print d symbols "+" and "-" in the second line. Symbol at jth position specifies an action which is applied to jth number in the princess' sequence. If multiple answers exist, choose any of them.

Sample Input

Input

2 5
3 2

Output

2
++

Input

5 5
1 2 3 4 5

Output

4
++-+


题意：输入n,k 然后输入n个正整数（每个数小于等于k 大于0）从第一个数开始加上或者减去这个数，使得当前的算式值在0~k之间，求这个算式的最大长度，
并输出这个算式的运算符；

思路：DP，定义dp[i][j]表示由前i个数能否得到j，能则dp[i][j]=1,否则为0；

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
int a[1005];
char s[1005];
bool dp[1005][1005];

int main()
{
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(dp,0,sizeof(dp));
        dp[1][a[1]]=1;
        int i,j;
        for(i=2;i<=n;i++)
        {
            int f=0;
            for(j=0;j<=k;j++)
            {
                if(dp[i-1][j])
                {
                    if(j+a[i]<=k) { dp[i][j+a[i]]=1; f=1; }
                    if(j>=a[i])   { dp[i][j-a[i]]=1; f=1; }
                }
            }
            if(f==0) break;
        }
        printf("%d\n",i-1);

        s[1]='+'; s[i]='\0'; i--;
        for(j=0;j<=k;j++)
        if(dp[i][j]) break;

        for(;i>=2;i--)
        {
            if(j>=a[i]&&dp[i-1][j-a[i]]) { s[i]='+'; j=j-a[i];}
            else { s[i]='-'; j=j+a[i]; }
        }
        puts(s+1);
    }
    return 0;
}