AcWing 3265. 再卖菜
原题链接
中等
作者:
把这题Ac了
,
2024-12-05 21:21:12
,
所有人可见
,
阅读 1
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
int st[N][N][N] = {0}; //记忆化搜索 记录状态的
int a[N],b[N]; // a是第二天,b是第一天
int n;
void dfs(int u,int x,int y){
if(st[u][x][y]) return ;
st[u][x][y] = 1;
//前n - 1个数确定了
if(u == n){
for(int i = 0;i < 2;i++){
if(2 * a[n] + i == b[n - 1] + b[n]){
for(int j = 1;j <= n;j++){
printf("%d ",b[j]);
}
exit(0);
}
}
}
for(int i = 0;i < 3;i++){
b[u + 1] = 3 * a[u] - x - y + i;
if(b[u + 1] > 0) dfs(u + 1,y,b[u + 1]);
}
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
for(int i = 1;i <= 2 * a[1];i++){
b[1] = i;
b[2] = 2 * a[1] - b[1];
dfs(2,b[1],b[2]);
b[2] = 2 * a[1] - b[1] - 1;
dfs(2,b[1],b[2]);
}
return 0;
}