Hdu 5781 ATM Mechine
链接
ATM Mechine
题意
Alice在银行的存款不超过K元，如果她取的钱超过了她在银行存款，就会被警告。
她最多可被警告W次，问你采用最优策略之后，期望取完所有钱的次数是多少
分析
E(i,j):存款的范围是[0,i],还可以被警告j次的期望值
取款金额为k时，有两种情况：没被警告，则余额大于等于k元，概率为(i-k+1)/(i+1)
被警告，则余额小于k元，概率为k/(i+1)，则转移方程：
$E(i,j)=min_{k=1}^{i}{\frac{i-k+1}{i+1} * E(i-k,j)+\frac{k}{i+1}*E(k-1,j-1)+1}$
Alice使用的是二分策略，那么在最坏情况下至多被警告$\left \lceil log_{2}{K} \right \rceil$
于是W:=min(W,15)就可以了
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<stdio.h>
#include<string.h>
#define min(a,b) a<b?a:b
const double INF=1e9;
const int N=2010;
double dp[N][20];
void init()
{
for(int i=0;i<N;i++){
for(int j=0;j<16;j++){
if(i==0)
dp[i][j]=0;
else
dp[i][j]=INF;
}
}
for(int i=1;i<N;i++){
for(int j=1;j<16;j++){
for(int k=1;k<=i;k++){
dp[i][j]=min(dp[i][j],dp[i-k][j]*(i-k+1)/(i+1)+dp[k-1][j-1]*k/(i+1)+1);
}
}
}
}
int main()
{
int k,w;
init();
while(scanf("%d%d",&k,&w)!=EOF){
int tm=min(w,15);
printf("%.6lf\n",dp[k][tm]);
}
return 0;
}
|
Hdu 5783 Divide the Sequence
链接
Divide the Sequence
题意
把长度为n的序列分成尽量多的连续段，使得每一段的每个前缀和都不小于0。保证有解。
分析
从后往前贪心分段即可。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<stdio.h>
#include<string.h>
const int N=1000010;
int a[N];
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
long long sum=0;
int ans=0;
for(int i=n;i>=1;i--){
sum+=a[i];
if(sum>=0){
sum=0;
ans++;
}
}
printf("%d\n",ans);
}
return 0;
}
|
Hdu 5791 Two
链接
Two
题意
已知A，B两个串，求A，B公共子序列的个数
分析
dp[i][j]表示A序列前i个数和B序列前j个数的相同子序列对的个数。
则 若a[i]!=b[j],dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
否则dp[i][j]=dp[i-1][j]+dp[i][j-1]+1；
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<stdio.h>
#include<string.h>
typedef long long LL;
const int N=1005;
const int MOD=(int)1e9+7;
LL dp[N][N];
int a[N],b[N];
LL solve(int n,int m)
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;
if(a[i]==b[j])
dp[i][j]=(dp[i][j]+1)%MOD;
else
dp[i][j]=(dp[i][j]-dp[i-1][j-1]+MOD)%MOD;
}
}
return dp[n][m];
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
printf("%lld\n",solve(n,m));
}
return 0;
}
|
Hdu 5792 World is Exploding
链接
World is Exploding
题意
给一个长度n的序列A，问有多少四元组(a,b,c,d)满足：4个数两两不同，
$1 <= a < b <= n，1 <= c < d <= n，A_a < A_b，A_c > A_d$
分析
定义：$rg(x)=∣{y∣x < y <= n,Ax < Ay}|$ 在Ax右边比它大的数的个数
$lg(x)=∣{y∣1 <= y < x,Ax < Ay}| $在Ax左边比它大的数的个数
$rs(x)=∣{y∣x < y <= n,Ax > Ay}| $在Ax右边比它小的数的个数
$ls(x)=∣{y∣1 <= y< x,Ax > Ay}| $在Ax左边比它小的数的个数
则answer=顺序对个数*逆序对个数-不符合情况的个数
不符合的情况分四种：
a=c时，$a < b,a < d,Aa < Ab,Aa > Ad$,个数=rg*rs,
a=d时，$a < b,c < a,Aa < Ab,Ac > Aa$，个数=rg*lg,
b=c时，$a < b,b < d,Aa < Ab,Ab > Ad$，个数=ls*rs,
b=d时，$a < b,c < b,Aa < Ab,Ac > Ab$，个数=ls*lg
以上值都可通过树状数组或线段树求出，题目数据较大，需离散化处理
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=50010;
const int MOD=(int)1e9+7;
int n,tree[N];
int ls[N],rs[N],lg[N],rg[N];
struct stu{
int val;
int id;
int rk;
}a[N];
bool cmp1(stu a,stu b)
{
return a.val<b.val;
}
bool cmp2(stu a,stu b)
{
return a.id<b.id;
}
int lowbit(int x)
{
return x&(-x);
}
void update(int pos)
{
for(int i=pos;i<=n;i+=lowbit(i))
tree[i]++;
}
int query(int pos)
{
int ans=0;
for(int i=pos;i>=1;i-=lowbit(i))
ans+=tree[i];
return ans;
}
int main()
{
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++){
scanf("%d",&a[i].val);
a[i].id=i;
}
sort(a+1,a+1+n,cmp1);
a[0].val=-1;
int cnt=1;
for(int i=1;i<=n;i++){
if(a[i].val==a[i-1].val)
a[i].rk=a[i-1].rk;
else
a[i].rk=cnt;
cnt++;
}
sort(a+1,a+1+n,cmp2);
memset(tree,0,sizeof(tree));
LL sumls=0,sumrs=0;
for(int i=1;i<=n;i++){
ls[i]=query(a[i].rk-1);
int tmp=query(a[i].rk);
lg[i]=i-1-tmp;
sumls+=ls[i];
update(a[i].rk);
}
memset(tree,0,sizeof(tree));
for(int i=n;i>=1;i--){
rs[i]=query(a[i].rk-1);
int tmp=query(a[i].rk);
rg[i]=n-i-tmp;
sumrs+=rs[i];
update(a[i].rk);
}
LL ans=sumls*sumrs;
for(int i=1;i<=n;i++){
ans-=(ls[i]*rs[i]+rg[i]*lg[i]+ls[i]*lg[i]+rg[i]*rs[i]);
}
printf("%lld\n",ans);
}
return 0;
}
|