# The Fourth Dimension Space

## 福大月赛 3月

A题 打表。。。

#include<iostream>
using namespace std;

/*
int dp[10000001];
int rex[10000];
int rey[10000];

int main()
{
freopen("out.txt","w",stdin);
int cnt=0;
int i,j;
for(i=1;i<=10000000;++i)
for(j=i<<1;j<=10000000;j+=i)
dp[j] += i;
for(i=220;i<=10000000;++i)
{
if(dp[i]<=10000000&&dp[dp[i]]<=10000000&&i==dp[dp[i]]&&i<dp[i])
{
cnt++;
printf("%d,%d,",i,dp[i]);
}

}

return 0;
}
*/

int dp[200][2]={220,284,1184,1210,2620,2924,5020,5564,6232,6368,10744,10856,12285,14595,17296,18416,63020,76084,66928,66992,67095,71145,69615,87633,79750,88730,100485,124155,
122265,139815,122368,123152,141664,153176,142310,168730,171856,176336,176272,180848,185368,203432,196724,202444,280540,365084,308620,389924,319550,430402,356408,
399592,437456,455344,469028,486178,503056,514736,522405,525915,600392,669688,
609928,686072,624184,691256,635624,712216,643336,652664,667964,783556,726104,796696,
802725,863835,879712,901424,898216,980984,947835,1125765,998104,1043096,1077890,
1099390,1154450,1189150,1156870,1292570,1175265,1438983,1185376,1286744,1280565,
1340235,1328470,1483850,1358595,1486845,1392368,1464592,1466150,1747930,1468324,
1749212,1511930,1598470,1669910,2062570,1798875,1870245,2082464,2090656,2236570,
2429030,2652728,2941672,2723792,2874064,2728726,3077354,2739704,2928136,2802416,
2947216,2803580,3716164,3276856,3721544,3606850,3892670,3786904,4300136,3805264,
4006736,4238984,4314616,4246130,4488910,4259750,4445050,4482765,5120595,4532710,
6135962,4604776,5162744,5123090,5504110,5147032,5843048,5232010,5799542,5357625,
5684679,5385310,5812130,5459176,5495264,5726072,6369928,5730615,6088905,5864660,
7489324,6329416,6371384,6377175,6680025,6955216,7418864,6993610,7158710,7275532,
7471508,7288930,8221598,7489112,7674088,7577350,8493050,7677248,7684672,7800544,
7916696,7850512,8052488,8262136,8369864,8619765,9627915,9071685,9498555,9199496,
9592504,9339704,9892936,9363584,9437056}
;

int main()
{

int n,m;

while(scanf("%d%d",&n,&m)!=EOF)

{

int t=0;

int i;

for(i=0;i<=105;i++)

{

if(dp[i][0]>=n&&dp[i][0]<=m&&dp[i][1]>=n&&dp[i][1]<=m)
t
++;
}

printf(
"%d\n",t);

for(i=0;i<=105;i++)

{

if(dp[i][0]>=n&&dp[i][0]<=m&&dp[i][1]>=n&&dp[i][1]<=m)
printf(
"%d %d\n",dp[i][0],dp[i][1]);
}

}

return 0;
}

D题 Cayley公式
n^(n-2)

G非常可恶的动规，还以为要用什么数学方法，DP真是博大精深啊。。。多谢AngelClover的提示
#include<iostream>
#include
<cstdio>
#include
<cmath>
using namespace std;
#define INF 999999999
#define OFFSET 4000
int dp[41][8001];

int main()
{

int n;

while(scanf("%d",&n)!=EOF)

{

int i,j;

for(i=0;i<=n;i++)

for(j=0;j<=8000;j++)
dp[i][j]
=INF;
dp[
0][OFFSET]=0;

int t;
scanf(
"%d",&t);
dp[
1][OFFSET+t]=0;
dp[
1][OFFSET-t]=0;

for(i=1;i<=n-1;i++)

{
scanf(
"%d",&t);

for(j=OFFSET-100*i;j<=OFFSET+100*i;j++)

{

if(dp[i][j]!=INF)

{

dp[i
+1][j+t]=min(dp[i+1][j+t],dp[i][j]+(j-OFFSET)*t);
dp[i
+1][j-t]=min(dp[i+1][j-t],dp[i][j]-(j-OFFSET)*t);
}

}

//for(j=OFFSET-10;j<=OFFSET+10;j++)

//{
//

//    printf("%d ",dp[i+1][j]);

//    }

//printf("\n");
}

double res=INF;

for(i=0;i<=8000;i++)

{

if(dp[n][i]<res)
res
=dp[n][i];
}

printf(
"%.2lf\n",res);

}

return 0;

}
I 离线算法 很强大啊，不过我在想 如果可以动态破坏的话，就只能用线段树了么？

#include<cstdio>
#include
<iostream>
#include
<algorithm>

/*
x是排好序的去掉的数
q[i].ID是询问的原本位置
q[i].kth是询问第kth个数
q按kth排序
ans就是答案
*/

#define MAX 50000
#define INF 0x7FFFFFFF

using namespace std;

struct Node
{

int ID;

int kth;

bool operator < (Node p)

{

return kth<p.kth;
}

}
;

int n;
int x[MAX];

int m;
Node q[MAX];

int ans[MAX];

int main()
{

while(scanf("%d",&n)!=EOF)

{

for(int i=1;i<=n;i++) scanf("%d",&x[i]);
x[
++n]=INF;
sort(x
+1,x+n+1);

int nn=1;

for(int i=2;i<=n;i++if(x[i]!=x[nn]) x[++nn]=x[i];
n
=nn;

scanf(
"%d",&m);

for(int i=1;i<=m;i++)

{
scanf(
"%d",&q[i].kth);
q[i].ID
=i;
}

sort(q
+1,q+m+1);

for(int i=1,j=1;i<=m;i++)//i代表第几个询问
{

while(x[j]-j<q[i].kth)
j
++;
ans[q[i].ID]
=(j-1)+q[i].kth;
}

for(int i=1;i<=m;i++
printf(
"%d\n",ans[i]);
putchar(
'\n');
}

return 0;
}

J题 动态规划 n^3水掉。。。 应该是有更好的方法，还要继续学习啊
#include<iostream>
#include
<algorithm>
#include
<cstdio>
#include
<cstring>
using namespace std;

#define INF 999999999
int dp[1001][1001];
char str[2000];
int c[1001];

int cc(int i,int j)
{
int res=0;
if(str[i]!='(')
res
+=c[i];
if(str[j]!=')')
res
+=c[j];
return res;
}

int main()
{

while(scanf("%s",str+1)!=EOF)
{

int i,j;
int n=strlen(str+1);
for(i=1;i<=n;i++)
{

for(j=i+1;j<=n;j++)
dp[i][j]
=INF;
}

for(i=1;i<=n;i++)
scanf(
"%d",&c[i]);
if(n&1)
{
printf(
"-1\n");
continue;
}

for(i=1;i<=n-1;i++)
dp[i][i
+1]=cc(i,i+1);
for(i=3;i<=n-1;i+=2)//i为区间长度
{

for(j=1;j<=n-i;j++)
{
int k;
int temp=INF;
for(k=2;k<i;k+=2)
{
if(dp[j][j+k-1]+dp[j+k][j+i]<temp)
temp
=dp[j][j+k-1]+dp[j+k][j+i];
}

dp[j][j
+i]=min(temp,dp[j+1][j+i-1]+cc(j,j+i));
}

}

printf(
"%d\n",dp[1][n]);

}

return 0;
}

初始state=0

( ( ) ) ) (
123456

( ( ) ) )

( ( ( ) )了

( ( ( ) ) (

(

)

((()))

posted on 2010-03-21 23:58 abilitytao 阅读(172) 评论(0)  编辑 收藏 引用