原题链接:CSP 201809-4 再卖菜
学习博客:ccf再卖菜
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=310;
int t;
int a[N],b[N];
bool f[N][N][N];//储存状态信息,也就是dfs的n,x,y
//分别是搜到第n天,b[n-1](求到了第n-1天的菜价),b[n](求到了第n天的菜价)
void dfs(int n,int x,int y)
{
if(f[n][x][y]) return;
f[n][x][y]=1;
if(n==t-1)//最后一天菜价特殊处理,所以n只用等于t-1就够了
{
if((3*a[n]-x)/2==a[t] || (3*a[n]-x+1)/2==a[t] || (3*a[n]-x+2)/2==a[t])
{
for(int i=1;i<=n;i++)
cout<<b[i]<<" ";
for(int i=0;i<3;i++)
{
if((3*a[n]-x+i)/2==a[t])
{
cout<<(3*a[n]-x-y+i);
exit(0);
}
}
}
return ;
}
for(int i=0;i<3;i++)
{
b[n+1]=3*a[n]-x-y+i;
if(b[n+1]>=1)
dfs(n+1,y,b[n+1]);
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0); std::cout.tie(0);
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>a[i];
}
for(int i=1;i<=2*a[1];i++)
{
b[1]=i,b[2]=2*a[1]-i;
dfs(2,i,b[2]);
//b[1]=i,b[2]=2*a[1]-i+1;
//dfs(2,i,b[2]);
}
return 0;
}