spoj PARTIT
2024-08-27 17:30:01
三维DP 第K字典序从左向右找 根据dp数组的值算出每一位该打印什么
代码:
#include <cstdio>
#include <cstring>
using namespace std;
long long memo[][][];
long long solve(int n, int m, int last)//n划分成m个数最小值为last;
{
if(n==)
{
if(m>=last) return ;
return ;
}
long long &ret = memo[n][m][last];
if(ret == -)
{
ret = ;
for(int i = last; (n+) * i <= m; ++i)
ret += solve(n-,m-i,i);
}
return ret;
} int main()
{
int T,M,N,K;
scanf("%d",&T);
while(T--)
{
scanf("%d %d %d",&M,&N,&K);
memset(memo,-,sizeof(memo));
int last = ;
for(int i = N-; i>; --i)
{
int tmp = ,j = last;
while(true)
{
if(tmp + solve(i-,M-j,j) >= K)//如果它的字典序超过了目标;
{
printf("%d ",j);
K -= tmp;
last = j;
M -= j;
break;
}
tmp += solve(i-,M-j,j);
++j;
}
}
printf("%d\n",M);
}
return ;
}
最新文章
- 通过Request对象对cookie的设置、获取
- ASP.NET Core 发布至Linux生产环境 Ubuntu 系统
- 自行实现PHP代码注解特性
- JavaScript的理解记录(3)
- WEB界面onload前的加载流程❤❤
- js之浏览器对象模型(BOM)
- 正则表达式(Regular Expression)
- Android 访问权限设置记录-存档留着有用!
- node安装 教程 + git初步
- zookeeper笔记--配置以及和spark hbase结合使用
- 【测试环境】java|jdk|ant
- mysql大写和小写问题
- DDoS攻击、CC攻击的攻击方式和防御方法
- CSS3 Hover 动画特效
- appium获取APP控件信息
- 学生成绩管理系统C++
- 通过TortoiseSVN进行文件(夹)外链 External File
- MVC基于角色权限控制--权限过滤
- Collection List接口
- spring mvc自定义注解--访问时验证