Description 一排n个怪兽，每个怪兽有一个重量，如果一只怪兽大于其相邻的一只重量比它小的怪兽那么就可以吃掉这只怪兽并合并其重量，一秒只会有一只怪兽吃掉旁边的怪兽，给出n-k秒后的k只怪兽重量，问是否存在一种合法的合并方案能够使得这n只怪兽变成k只怪兽 Input 第一行一整数n表示初始状态怪兽数量，之后n个整数a[i]表示第i只怪兽的重量，然后输入一整数k表示最后怪兽数量，之后k个整数b[i]表示第i只怪兽的重量(1<=k<=n<=500,1<=a[i]<=1e6,1<=b[i]<=5e8) Output 如果存在合法方案，则按时间顺序输出每一秒哪一只怪兽吃了左边相邻怪兽还是右边相邻怪兽，否则输出NO Sample Input 6 1 2 2 2 1 2 2 5 5 Sample Output YES 2 L 1 R 4 L 3 L Solution 如果合法，那么就是把a序列分成k段，然后每一段段和等于b序列的一个元素，且每一段内存在一种合法方案使得能够变成一只怪兽，所以从左到右给a分段，如果分不成一段则无解，否则对于每一段每次拿重量最大的怪兽吃旁边的怪兽，如果没有能吃的就无解 Code、
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 1111 int n,k,a[maxn],b[maxn],c[maxn],gg; typedef pair<int,int>P; vector<P>ans; void solve(int l,int r,int plus) { if(l==r)return ; for(int i=l;i<=r;i++)c[i-l+1]=a[i]; int m=r-l+1; for(int k=1;k<=r-l;k++) { int pos=1; for(int i=1;i<=m;i++) { if(c[i]>c[pos])pos=i; else if(c[i]==c[pos]) { if(i<m&&c[i+1]<c[i]||i>1&&c[i-1]<c[i]) pos=i; } } if(pos==m) { if(c[m-1]==c[m]) { gg=1; return ; } c[m-1]+=c[m]; ans.push_back(P(m+plus,0)); } else if(pos==1) { if(c[1]==c[2]) { gg=1; return ; } c[2]+=c[1]; for(int i=1;i<m;i++)c[i]=c[i+1]; ans.push_back(P(1+plus,1)); } else { if(c[pos-1]<c[pos]) { c[pos]+=c[pos-1]; for(int i=pos-1;i<m;i++)c[i]=c[i+1]; ans.push_back(P(pos+plus,0)); } else if(c[pos+1]<c[pos]) { c[pos]+=c[pos+1]; for(int i=pos+1;i<m;i++)c[i]=c[i+1]; ans.push_back(P(pos+plus,1)); } else { gg=1; break; } } m--; } } int main() { while(~scanf("%d",&n)) { ans.clear(); for(int i=1;i<=n;i++)scanf("%d",&a[i]); scanf("%d",&k); for(int i=1;i<=k;i++)scanf("%d",&b[i]); gg=0; int j=1,num=0; for(int i=1;i<=k;i++) { if(gg)break; int pre=j; while(j<=n&&num<b[i])num+=a[j],j++; if(num>b[i]|| j==n+1&&num<b[i]) { gg=1; break; } solve(pre,j-1,i-1); num=0; } if(j!=n+1)gg=1; printf("%s\n",gg?"NO":"YES"); if(!gg) for(int i=0;i<ans.size();i++) printf("%d %c\n",ans[i].first,ans[i].second?'R':'L'); } return 0; }