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

題目鏈接

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

Description

— 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

2 5
3 2

2
++

5 5
1 2 3 4 5

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;
}