[网络流24题]魔术球问题

NC213818. [网络流24题]魔术球问题

描述

假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可放11 个球。
编程任务：对于给定的n，计算在n根柱子上最多能放多少个球。

输入描述

第1 行有1个正整数n，表示柱子数。

输出描述

程序运行结束时，将n 根柱子上最多能放的球数以及相应的放置方案输出。文件的第一行是球数。接下来的n行，每行是一根柱子上的球的编号。

示例1

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 4ms, 内存消耗: 428K, 提交时间: 2022-07-08 13:51:45

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const int maxn=60;
int n,m,s,t;
int f[60][60];
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin>>n;
    int p=(n*(n+2)+(n&1)-2)/2;
    cout<<p<<"\n";
    for(int i=1;i<=p;i++)
        for(int j=1;j<=n;j++){
            int num=f[j][f[j][0]];
            if(!num||(((int)sqrt(num+i))*((int)(sqrt(num+i))))==num+i){
                f[j][++f[j][0]]=i;
                break;
            }
        }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=f[i][0];j++)
            cout<<f[i][j]<<" ";
        cout<<"\n";
    }
}