本文主要是介绍poj1722 SUBTRACT，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：一列数共n个，每次选择一个i，在第i和i+1个数之间添加减号，然后用差代替这两个数。最后使得n个数合成一个数T。求减号添加的位置顺序。
思路：dp(背包)。背包记录路径，就可以得到这个序列每个位置添加的是加号还是减号。然后怎么得到减号添加的顺序呢，按顺序扫描这个序列的符号，如果是加减相间的（第一个符号必须是‘-’，如“-+-+-+”），就继续往下扫，如果发现连续两个同号或者扫描到了末尾，那么这个位置就应该添加。然后模拟一下合并的过程，直到最后剩下一个数就可以了。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>using namespace std;int a[110];
bool dp[110][20010];
int pre[110][20010];
int sign[110];int main(){int n,t;while(cin>>n>>t){t+=10000;for(int i=1;i<=n;i++)scanf("%d",&a[i]);memset(dp,0,sizeof(dp));dp[0][10000]=1;//背包，注意前两个数的符号 for(int i=1;i<=n;i++){for(int j=0;j<=20000;j++){if(dp[i-1][j]){if(i==1){dp[i][j+a[i]]=1;pre[i][j+a[i]]=-1;continue;}if(i==2){dp[i][j-a[i]]=1;pre[i][j-a[i]]=1;continue;}dp[i][j+a[i]]=1;pre[i][j+a[i]]=-1;dp[i][j-a[i]]=1;pre[i][j-a[i]]=1;}}}int cur=t;for(int i=n;i>=1;i--){sign[i]=-pre[i][cur];cur+=pre[i][cur]*a[i];}int time=n-1;while(time){int k=1;while(sign[k]!=sign[k+1]&&k<=time){ //直到发现相邻同号 k++;}for(int i=k;i<=time;i++){ //模拟合并 sign[i]=sign[i+1];}cout<<k-1<<endl; //输出减号添加位置 time--;}}return 0;
}这篇关于poj1722 SUBTRACT的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
