早上随便搞搞t1t3就开始划水了，t2一看就是组合数学看着肚子疼...结果t1t3都a了？？感天动地。
从小到大排序，从前到后枚举i，表示i是整个背包中不选的物品中代价最小的那个，即i不选，1到i-1全部都要选，i+1到n做背包（此时容量为m-pre），极限复杂度$O(n^3)$，可是我们在中间判断一下，当剩余容量比当前i代价小，break。可以减掉很大的复杂度！（cena评测最慢0.04s~
或者可以在枚举i时倒着枚举，每次背包就可以$O(n)$解决了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define RG register using namespace std; const int mod = 1000000007; int n, m, a[1005]; int f[1005]; int main ( ) { freopen ( "gift.in", "r", stdin ); freopen ( "gift.out", "w", stdout ); scanf ( "%d%d", &n, &m ); for ( int i = 1; i <= n; i ++ ) { scanf ( "%d", &a[i] ); } sort ( a + 1, a + 1 + n ); ll ans = 0; int sum = 0; for ( RG int i = 1; i <= n; i ++ ) { memset ( f, 0, sizeof ( f ) ); f[0] = 1; for ( RG int k = i + 1; k <= n; k ++ ) { if ( m - sum < a[k] ) break; for ( RG int j = m - sum; j >= a[k]; j -- ) { f[j] = ( f[j] + f[j-a[k]] ) % mod; } } for ( RG int j = max ( m - sum - a[i] + 1, 0 ); j <= m - sum; j ++ ) ans = ( ans + f[j] ) % mod; sum += a[i]; } printf ( "%d", ans ); return 0; }
题意是要求该序列-1的累加和永远小于等于1的累加和的概率。经典的卡特兰数问题，在坐标系中，可以把-1看成向上走，把1看成向右走，最终目标是计算从原点走到$(n,m)$并且过程中不能超出到$y=x$这条直线的方案数。方案数为$C_{m+n}^m-C_{m+n}^{m-1}$，即$frac{n-m+1}{n+1}$
#include<iostream> #include<cstdio> using namespace std; int main ( ) { freopen ( "fseq.in", "r", stdin ); freopen ( "fseq.out", "w", stdout ); int T; scanf ( "%d", &T ); while ( T -- ) { int n, m; scanf ( "%d%d", &n, &m ); if ( n < m ) printf ( "0.000000 " ); else printf ( "%.6lf", ( double ) ( n - m + 1 ) / ( double ) ( n + 1 ) ); } return 0; }
感觉我的方法是碰巧遇到可以过的类型了...如果题目不合法的对应关系改一下马上就会挂。
但是题目给的是对应不能相同嘛~我定义的$dp[dep][up][tot]$分别表示当前数的位置，是否顶上界，已经填了多少个数（抛开前导零，记忆化的时候会发现，除了顶上界的情况只会计算一次并且不会第二次返回，不顶上界的情况计算一次后每次都直接返回了，不管前面填的什么数和后面将填什么数...
可是对于这道题它恰好就是对的！在不顶上界的情况，所有数字都可以填，并且所有数字都有相同的不合法情况个数！所以直接记忆化就没有问题...
可是$yuli$dalao（%%%指出，只要把题稍微改一改，比如对应位置不能同时为质数之类的...每个数的方案数就不一样了！
所以正解是枚举数的长度，从前后同时填数即可。
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; ll dp[20][2][20]; int num[20], fi[20]; ll dfs ( int dep, int up, int tot ) { if ( dp[dep][up][tot] ) return dp[dep][up][tot]; if ( !dep && tot ) return 1; if ( !dep ) return 0; int MA = up ? num[dep] : 9; ll res = 0; for ( int i = 0; i <= MA; i ++ ) { if ( i == 0 && !tot ) res += dfs ( dep - 1, up && i == MA,tot ); else if ( fi[tot + 1] != i ) { fi[dep] = i; res += dfs ( dep - 1, up && i == MA, tot + 1 ); fi[dep] = -1; } } dp[dep][up][tot] = res; return res; } ll work ( ll x ) { int cnt = 0; memset ( fi, -1, sizeof ( fi ) ); memset ( dp, 0, sizeof ( dp ) ); while ( x ) { num[++cnt] = x % 10; x /= 10; } return dfs ( cnt, 1, 0 ); } int main ( ) { freopen ( "lucky.in", "r", stdin ); freopen ( "lucky.out", "w", stdout ); ll x, y; scanf ( "%I64d%I64d", &x, &y ); ll xx = work ( x - 1 ), yy = work ( y ); printf ( "%I64d", yy - xx ); } // wans
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll l,r,dp[12][2][2]; int tot,dig[30]; bool vis[12][2][2]; ll dfs(int dep,bool lf_up,bool rg_up) { if(vis[dep][lf_up][rg_up]) return dp[dep][lf_up][rg_up]; if(dep == tot - dep + 1) { if(lf_up && rg_up) return dig[dep]; else if(! lf_up) return 10; else if(lf_up) return dig[dep] + 1; } if(dep > tot - dep + 1) { if(lf_up && rg_up) return 0; return 1; } vis[dep][lf_up][rg_up] = true; int up = lf_up ? dig[tot - dep + 1] : 9; ll res = 0; for(int i = 0;i <= up;i ++) for(int j = 0;j <= 9;j ++) { if(i == j) continue; if(dep == 1 && i == 0) continue; bool upup; if(j > dig[dep]) upup = true; else if(j < dig[dep]) upup = false; else upup = rg_up; res += dfs(dep + 1,lf_up && (i == dig[tot - dep + 1]),upup); } return dp[dep][lf_up][rg_up] = res; } ll solve(ll s) { memset(vis,0,sizeof(vis)); ll ss = s,ans = 0; tot = 0; while(s) { dig[++ tot] = s % 10; s /= 10; } ans += dfs(1,1,0); for(int i = 1;i <= tot;i ++) dig[i] = 9; for(tot = tot - 1;tot >= 1;tot --) { memset(vis,0,sizeof(vis)); ans += dfs(1,1,0); } return ans; } int main( ) { freopen("lucky.in","r",stdin); freopen("lucky.out","w",stdout); scanf("%I64d%I64d",& l,& r); ll ans1 = solve(l - 1); ll ans2 = solve(r); printf("%I64d",ans2 - ans1); } //yuli