31 条题解
-
5
ljt12138 LV 10 @ 2016-11-14 16:23:52
问题的数学模型是从前n个数字中选取尽可能少的个数，使得其和取遍1..m中所有的值。不难想到用dp[i][j]表示前i个数字选择取遍1..j的尽可能少的个数。有
dp[0][0] = 0
dp[i][j] = min{dp[i-1][j], dp[i-1][k]+1 | k >= i+1, 且j-i <= k < j}
由于不等式i < j <--> dp[a][i] <= dp[a][j]显然成立，所以dp[i-1][k]取最小值必然在k = max{i+1, j-i}。也不难证明这种方法既不重复又不遗漏，因此用数组cnt根据决策统计即可。#include <iostream> #include <cstdio> #include <cstring> using namespace std; int dp[1005][1005]; int cnt[1005][1005]; int main() { int n; cin >> n; memset(dp, 127/3, sizeof dp); memset(cnt, 0, sizeof cnt); dp[0][0] = 0; cnt[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j <= n; j++) { //if (j <= i) continue; dp[i][j] = dp[i-1][j]; int k = max(i-1, j-i); dp[i][j] = min(dp[i][j], dp[i-1][k]+1); if (dp[i][j] == dp[i-1][j]) cnt[i][j] += cnt[i-1][j]; if (dp[i][j] == dp[i-1][k]+1) cnt[i][j] += cnt[i-1][k]; } } cout << dp[n][n] << " " << cnt[n][n] << endl; return 0; } -
3
/* 首先有这么一个结论：对任意n：1,2,4,8,......总是一个最优方案. 那么很容易知道 最少个数为log2n+1 假设第k-1个数是a[k-1],前k-1个数能达成的最大的连续的数是sum, 那么第k个数的范围一定是a[k-1]+1到sum+1. 然后用动态规划来求解方案总数 用f[count,last,max] 表示count个数、最后的数（也是最大的）为last、能组成1到max中所有正整数的方案数 然后状态转移方程就很容易出来了 仔细看代码叭~好晚了要睡觉咯~233333 注意到n最大1000 所以ans最大为10 所以第一维开到11 二三维最大就是1000咯 */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; const int maxn=1005; int n; int ans; int tot; int f[11][maxn][maxn]; int main() { cin>>n; ans=(int)log2(n)+1; f[1][1][1]=1; for(int i=1;i<ans;i++) for(int j=i;j<=(1<<(i-1));j++) for(int k=i;k<=((1<<i)-1);k++) if(f[i][j][k]) for(int p=j+1;p<=k+1;p++) { if(p+k<=n)//如果加起来在范围内 f[i+1][p][k+p]+=f[i][j][k]; else//加起来不在范围内 f[i+1][p][n]+=f[i][j][k]; } for(int i=1;i<=n;i++) tot+=f[ans][i][n]; cout<<ans<<" "<<tot<<endl; return 0; } -
0
/* 这里不是采用动态规划，用dfs + 剪枝, 注意提前一个节点剪枝, 参考了博客： https://blog.csdn.net/a_bright_ch/article/details/83786942 这里的解释很详细 */ #include <algorithm> #include <cmath> #include <iostream> #include <string> using namespace std; const int maxn = 1002; int len, ans, n; void dfs(int k, int maxx, int sum) { // k为dfs树层数, maxx为最大的是(最后的数, 当前数), sum为和 // 若不前剪枝, 会超时 // if (k == len) { // if (n <= sum) ans++; // return; // } if (k == len) { // ans += (sum * 2 + 1) - (n - 1); int num = sum - maxx + 1; //下一节点的孩子数 //下面给出下一节点的sum的范围 // sum + maxx + 1 <= newsum <= 2 * sum + 1; if (n <= 2 * sum + 1) { // n <= newsum if (n <= sum + maxx + 1) ans += num; //sum - maxx + 1 else ans += num - (n - sum - maxx - 1); //2 * sum + n - 2 } return; } for (int i = maxx + 1; i <= sum + 1; i++) dfs(k + 1, i, sum + i); } int main() { cin >> n; len = (int)log2(n) + 1; dfs(1, 0, 0); // maxx, sum都是上一节点的值 cout << len << " " << ans << endl; system("pause"); return 0; } -
0
#include <bits/stdc++.h>
using namespace std;
int n;
int f[1010][1010];
int cnt[1010][1010];int main()
{
cin >> n;
int ans = 1,count = 2;
while(count <= n){
ans++;
count *= 2;
}
cout << ans << " ";
////////////////////////////////////////////////
memset(f,0,sizeof(f));
memset(cnt,0,sizeof(cnt));
f[0][0] = 0;
cnt[0][0] = 1;for(int i = 1; i <= n; i++){
for(int j = 0; j <= n; j++){
int help = max(i-1,j-i);
if(f[i-1][j] <= f[i-1][help]+1){
f[i][j] = f[i-1][j];
cnt[i][j] += cnt[i-1][j];
}
else{
f[i][j] = f[i-1][help]+1;
cnt[i][j] += cnt[i-1][help];
}
}
}cout << cnt[n][n];
return 0;
}
这....为啥是错的啊 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
- -! 动规...... -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms第一次只加了数学方法的节支（有点写萎了）
没有用倒数第二步时直接计算答案的方法有一个点1400+ms然后把数学方法改好又加上倒数第二步时直接计算答案就秒杀了= =
另外要小心1的情况
强烈建议加入512这个点><
答案是10 1869956813 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 322ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 431ms
├ 测试数据 07：答案正确... 775ms
├ 测试数据 08：答案正确... 9ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|- -
0
EZ_ray040123 LV 10 @ 2009-06-15 18:15:34
oimaster 所谓的秒杀程序有错
输入： 128
输出：7 0
不可能是0吧.....我的是 435939
curimit 的是 436003
不知道哪个对建议测试数据应加上 128
-
0
搜索在最后一步时直接计算出答案可以秒杀。
增加的种数=max-min+1但是精益求精，在搜索倒数第二步时也可以直接计算出答案。
增加的种数是一个非常复杂的分段函数。真是太复杂了，算了好长时间。下面是搜索到倒数第二步时直接计算答案的程序。
program dangao;
var
n,m,tot:longint;
ans:int64;procedure search(lev,last:longint);
var i,e,x,y:longint;
begin
if tot>=n then e:=n else e:=tot+1;
if lev=m-1 then
begin
x:=last+1; if xtot+1 then y:=tot+1;
if xtot+1 then y:=tot+1;
if x -
0
秒杀的程序：
program Vijos_P1154;
var
f:array[1..10,1..1000,1..1000] of longint;
n,k,count,last,max,i,total:longint;
begin
readln(n);
k:=trunc(ln(n)/ln(2))+1;
fillchar(f,sizeof(f),0);
f[1,1,1]:=1;
for count:=1 to k-1 do
for last:=count to 1 shl (count-1) do
for max:=count to 1 shl count-1 do
if f[count,last,max]>0 then
for i:=last+1 to max+1 do
if max+i -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 166ms
├ 测试数据 07：答案正确... 166ms
├ 测试数据 08：答案正确... 150ms
├ 测试数据 09：答案正确... 166ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：648ms
原来题解是在搜完倒数第二个的时候手工判断最后一个能取什么值....
加上这个就能A了，不过还是不够快~ -
0
狂晕 这题搜索过不了丫...
怎么是dp...
program mzn;
var j,t,n,pre,last,max,i,k:longint;
a:array[1..10]of integer;
f:array[1..10,1..1000,1..1000]of longint;
total:longint;begin
readln(n);
k:=trunc(ln(n)/ln(2))+1; write(k,' ');
for i:=1 to k do
a[i]:=1 shl (i-1);
f[1,1,1]:=1;
for pre:=1 to k-1 do
for last:=pre to a[pre] do
for max:=1 to n do
begin
if f[pre,last,max]>0 then
begin
for i:=last+1 to max+1 do
begin
if max+i
ljt12138
LV 10
@ 2016-11-14 16:23:52
