SUBTRACT
| Time Limit: 1000MS | Memory Limit: 10000K | |||
| Total Submissions: 2677 | Accepted: 1182 | Special Judge | ||
Description
We are given a sequence of N positive integers a = [a1, a2, ..., aN] on which we can perform contraction operations.
One contraction operation consists of replacing adjacent elements ai and ai+1 by their difference ai-ai+1. For a sequence of N integers, we can perform exactly N-1 different contraction operations, each of which results in a new (N-1) element sequence.
Precisely, let con(a,i) denote the (N-1) element sequence obtained from [a1, a2, ..., aN] by replacing the elements ai and ai+1 by a single integer ai-ai+1 :
con(a,i) = [a1, ..., ai-1, ai-ai+1, ai+2, ..., aN]
Applying N-1 contractions to any given sequence of N integers obviously yields a single integer.
For example, applying contractions 2, 3, 2 and 1 in that order to the sequence [12,10,4,3,5] yields 4, since :
Given a sequence a1, a2, ..., aN and a target number T, the problem is to find a sequence of N-1 contractions that applied to the original sequence yields T.
One contraction operation consists of replacing adjacent elements ai and ai+1 by their difference ai-ai+1. For a sequence of N integers, we can perform exactly N-1 different contraction operations, each of which results in a new (N-1) element sequence.
Precisely, let con(a,i) denote the (N-1) element sequence obtained from [a1, a2, ..., aN] by replacing the elements ai and ai+1 by a single integer ai-ai+1 :
con(a,i) = [a1, ..., ai-1, ai-ai+1, ai+2, ..., aN]
Applying N-1 contractions to any given sequence of N integers obviously yields a single integer.
For example, applying contractions 2, 3, 2 and 1 in that order to the sequence [12,10,4,3,5] yields 4, since :
con([12,10,4,3,5],2) = [12,6,3,5]
con([12,6,3,5] ,3) = [12,6,-2]
con([12,6,-2] ,2) = [12,8]
con([12,8] ,1) = [4]
Given a sequence a1, a2, ..., aN and a target number T, the problem is to find a sequence of N-1 contractions that applied to the original sequence yields T.
Input
The
first line of the input contains two integers separated by blank
character : the integer N, 1 <= N <= 100, the number of integers
in the original sequence, and the target integer T, -10000 <= T <=
10000.
The following N lines contain the starting sequence : for each i, 1 <= i <= N, the (i+1)st line of the input file contains integer ai, 1 <= ai <= 100.
The following N lines contain the starting sequence : for each i, 1 <= i <= N, the (i+1)st line of the input file contains integer ai, 1 <= ai <= 100.
Output
Output
should contain N-1 lines, describing a sequence of contractions that
transforms the original sequence into a single element sequence
containing only number T. The ith line of the output file should contain
a single integer denoting the ith contraction to be applied.
You can assume that at least one such sequence of contractions will exist for a given input.
You can assume that at least one such sequence of contractions will exist for a given input.
Sample Input
5 4 12 10 4 3 5
Sample Output
2 3 2 1
Source
难是真的不难，一开始看到了这种操作，感觉后效性处理只能够用区间dp
然后我考虑了一下合并顺序的影响，突然发现只是+和-的区别，那就是一个非常明显的线性dp了
但是我不知道为什么感觉做不了，看了一下，结果不会设计状态
现在想想其实就很明显，很经典。。
感觉我的dp的方法不是那么明显
现在想想其实就很明显，很经典。。
感觉我的dp的方法不是那么明显
主要还是看经验，这个状态设计和背包是一类的
现在想想我会的状态设计也就那几种
一个是背包一类的，一个是区间dp一类，一个是LCS还有f[i]表示第i个选上
一个是树形dp的，一个是用一个维度来表示当前这个数字选不选，一个是环形的2倍范围
一个是传纸条的那种，也就是现在到了哪里，但是比较长
一个是背包一类的，一个是区间dp一类，一个是LCS还有f[i]表示第i个选上
一个是树形dp的，一个是用一个维度来表示当前这个数字选不选，一个是环形的2倍范围
一个是传纸条的那种，也就是现在到了哪里，但是比较长
按我现在学到了状压dp来算的话应该就这些，
代码
#include <iostream> #include <stdio.h> #include <algorithm> #include <cmath> #include <math.h> #include <map> #include <string.h> #define ll long long using namespace std; inline int read() { char c=getchar();int a=0,b=1; for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1; for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b; } int n,a[101],f[101][30001],T; int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); n=read();T=read(); for(int i=1;i<=n;i++) { a[i]=read(); } f[1][a[1]+10000]=1; f[2][a[1]-a[2]+10000]=-1; for(int i=3;i<=n;i++) { for(int j=0;j<=20000;j++) { if(f[i-1][j]!=0) { f[i][j+a[i]]=1; f[i][j-a[i]]=-1; } } } int ans[1001]={};int now=T+10000,cnt=0; for(int i=n;i>=2;i--) { ans[i]=f[i][now]; if(ans[i]==-1)now+=a[i]; else if(ans[i]==1)now-=a[i]; } for(int i=2;i<=n;i++) { if(ans[i]==1) { cout<<i-cnt-1<<endl; cnt++; } } for(int i=2;i<=n;i++) { if(ans[i]==-1)cout<<1<<endl; } return 0; }