正解:dfs+dp
解题报告:
第一眼以为小凯的疑惑
ummm说实话没看标签我还真没想到正解:D
本来以为这么多年前的noip应该不会很难:D
看来还是太菜了鸭QAQ
然后听说题解都可以被6,6 or 7,8的数据卡掉?
不管不管先把题解的思路放下qwq
(话说其实我觉得虽然会被卡掉但其实还挺妙的了呢,,,至少我这种菜鸡想不出来,,,好傻逼啊我QAQ
大概说下,就是dfs+dp(,,,我好像说了句废话?QAQ
分别详细说下这俩趴qwq
dfs(i,mx):枚举到第i个数了,然后连续最大能表示数是mx
然后显然可以让邮票面值单调递增,且第i个不能大于mx+1(否则mx+1就无法表示了QAQ)
然后每次dp算下能表示的mx,继续dfs
dp(i):第1到第i个数的连续最大能表示数
开个f[i]存的是i最少可以用几张邮票表示
然后就可以了qwq
但是似乎复杂度是错的,,,
然后另外一个正解是打表,,,
umm,,,算了我放弃我估计我是搞不出来了的QAQ
不过研究了半天之后在讨论区看到说模拟退火可以过这题?
然而好像又说7 8的数据是不欧克的,也不知道是时间不欧克还是答案是WA的鸭QAQ
不管先先放下讨论区里大佬说的模拟退火的代码qwq
现在是先看不懂的QAQ就只是mk下不会研究,等学了之后再说QAQ
#include<iostream>
#include<cstring>
using namespace std;
][];//[num][used]
];
];
],maxnum;
;
,times=;//not best
bool rand(int mdf){
+))%>rate);
}
int n,k;
int fcannot,lastcan;
int now;
int main(){
cin>>n>>k;
for(int _233=times;_233;_233--){
memset(can,,sizeof(can));
memset(cangen,,sizeof(cangen));
can[][]=true;
cangen[]=true;
choose[]=;
;i<=n;i++){
can[i][i]=true;
cangen[i]=true;
}
fcannot=n+;
lastcan=n;
;i<k;i++){
;j++){
if(!cangen[j]){
fcannot=j;
break;
}
}
now=fcannot;
;j<;j++){
if(rand(j)){
>choose[i-]){
now-=;
}else{
break;
}
}
}
choose[i]=now;
;i<=lastcan;i++){
;j<n;j++){
if(can[i][j]){
)continue;
can[i+now][j+]=true;
cangen[i+now]=true;
lastcan=max(lastcan,i+now);
}
}
}
}
;j++){
if(!cangen[j]){
fcannot=j;
break;
}
}
fcannot--;
if(fcannot>maxnum){
;i<;i++){
bestsel[i]=choose[i];
}
maxnum=fcannot;
}
}
;i<k;i++){
cout<<bestsel[i]<<" ";
}
cout<<endl;
cout<<"MAX="<<maxnum;
}
QAQQQQQ