计算24点

/*———————————————————————
                      24点娱乐程序之一

10.21测试,

QAQ(虎掌一枚),居然全打暴力。

  T1能看出来是DP,但实质上想不到丰富奇伎淫巧,果断暴搜(20)。

  T2应当比较轻松,写完正解跟暴力对拍,错了QAQ,间接交了强力。

  T3压根没往floyd想,交暴力。

T1(cogs 1292.打砖块)

暴力:

图片 1 1
#include<cstdio> 2 #include<iostream> 3 #define mysister
4 using namespace std; 5 const int maxn=50; 6 int read(){ 7 int
x=0,f=1;char ch=getchar(); 8
while(ch<‘0’||ch>’9′){if(ch==’-‘)f=-1;ch=getchar();} 9
while(ch>=’0’&&ch<=’9’){x=x*10+ch-‘0’;ch=getchar();} 10 return
x*f; 11 } 12 void Emine(){ 13 freopen(“brike.in”,”r”,stdin); 14
freopen(“brike.out”,”w”,stdout); 15 } 16 int
n,m,a[maxn][maxn],ans=0,vis[maxn][maxn]; 17 void dfs(int cc,int
aa,int bb){ 18 if(cc==m){ 19 int anss=0; 20 for(int i=0;i<n;++i) 21
for(int j=0;j<n-i;++j) 22 if(vis[i][j]) 23 anss+=a[i][j]; 24
ans=max(anss,ans); 25 return; 26 } 27 if(bb>=n-aa||aa>=n) return;
28 for(int i=bb;i<n-aa;++i) 29
if(aa==0||(vis[aa-1][i]&&vis[aa-1][i+1])){ 30 vis[aa][i]=1;
31 dfs(cc+1,aa,i+1);dfs(cc+1,aa+1,0); 32 vis[aa][i]=0; 33 } 34 } 35
int main(){ 36 Emine(); 37 n=read(),m=read(); 38 for(int i=0;i<n;++i)
39 for(int j=0;j<n-i;++j) 40 a[i][j]=read(); 41 dfs(0,0,0); 42
printf(“%dn”,ans); 43 return 0; 44 } View Code

正解:

图片 2 1
//f[i][j][k]表示停止到第i行,总共已经选j个砖块,个中第i行已经选了前k个砖块的最大值。
2 #include<cstdio> 3 #include<cstring> 4
#include<iostream> 5 #include<algorithm> 6 #define maxn
55 7 using namespace std; 8 void Emine(){ 9
freopen(“brike.in”,”r”,stdin); 10 freopen(“brike.out”,”w”,stdout); 11 }
12 int
n,m,v[maxn][maxn],s[maxn],sum[maxn][maxn],ans,f[maxn][10*maxn][maxn];
13 int main(){ 14 Emine(); 15 scanf(“%d%d”,&n,&m); 16 for(int
i=1;i<=n;i++)for(int j=i;j<=n;j++) scanf(“%d”,&v[j][i]); 17
for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)
sum[i][j]=sum[i][j-1]+v[i][j]; 18 for(int i=1;i<=n;i++)
s[i]=s[i-1]+i; 19 memset(f,-333,sizeof(f)); f[0][0][0]=0; 20
for(int i=1;i<=n;i++State of Qatar{//结束到第i行 21 for(int
j=0;j<=min(m,s[i]卡塔尔;j++卡塔尔(قطر‎{//总共已经选j个砖块 22 for(int
k=0;k<=min(i,j卡塔尔国;k++卡塔尔国{//第i行已经选了前k个砖块 23 for(int
p=max(k-1,0卡塔尔国;p<i&&s[p]<=j-k;p++) 24
f[i][j][k]=max(f[i][j][k],f[i-1][j-k][p]+sum[i][k]);
25 ans=max(ans,f[i][j][k]); 26 } 27 } 28 } 29 printf(“%dn”,ans);
30 return 0; 31 } View Code

T2(luogu 1631.行列合并)

暴力:

图片 3 1
#include<cstdio> 2 #include<cstring> 3
#include<iostream> 4 #include<algorithm> 5
#include<queue> 6 #include<vector> 7 #define ll long long
8 using namespace std; 9
priority_queue<ll,vector<ll>,greater<ll> > q; 10 int
n;ll a[100005],b[100005]; 11 int main(){ 12 scanf(“%d”,&n); 13
for(int i=1;i<=n;i++)scanf(“%lld”,&a[i]); 14 for(int
i=1;i<=n;i++)scanf(“%lld”,&b[i]); 15 for(int i=1;i<=n;i++) 16
for(int j=1;j<=n;j++) 17 q.push(a[i]+b[j]); 18 for(int
i=1;i<=n;i++){ 19 printf(“%lld “,q.top()); 20 q.pop(); 21 } 22 return
0; 23 } View Code

正解:

图片 4 1
#include<cstdio> 2 #include<iostream> 3
#include<queue> 4 #include<algorithm> 5 #define maxn
100005 6 using namespace std; 7 int a[maxn],b[maxn],ans[maxn]; 8
priority_queue <int> q; 9 int main(){ 10 int n;cin>>n; 11
for(int i=1;i<=n;i++)scanf(“%d”,&a[i]); 12 for(int
i=1;i<=n;i++){ 13 scanf(“%d”,&b[i]); 14 q.push(b[i]+a[1]); 15 }
16 for(int i=1;i<=n;i++) 17 for(int j=2;j<=n;j++){ 18 int
temp=b[i]+a[j]; 19 if(temp>q.top()) break; 20 else{ 21 q.pop();
22 q.push(temp); 23 } 24 } 25 for(int i=1;i<=n;i++){ 26
ans[n-i+1]=q.top(); 27 q.pop(); 28 } 29 for(int i=1;i<=n;i++) 30
cout<<ans[i]<<” “; 31 return 0; 32 } View Code

T3(cogs 501.微细密度路径)

暴力:

图片 5 1
#include<cstdio> 2 #include<cstring> 3
#include<iostream> 4 #include<algorithm> 5 using namespace
std; 6 int
cnt,n,m,x,y,q,next[100001],last[100001],to[100001],cost[100001],b[101][101];
7 double ans,a[101][101]; 8 int read(){ 9 int x=0,f=1;char
ch=getchar(); 10
while(ch<‘0’||ch>’9′){if(ch==’-‘)f=-1;ch=getchar();} 11
while(ch>=’0’&&ch<=’9’){x=x*10+ch-‘0’;ch=getchar();} 12 return
x*f; 13 } 14 void Emine(){ 15 freopen(“path.in”,”r”,stdin); 16
freopen(“path.out”,”w”,stdout); 17 } 18 void dfs(int num,int sum,int
len){ 19 if(num==y){ 20 if((double)sum/(double)len<ans)
ans=(double)sum/(double)len; 21 return ; 22 } 23 int t=last[num]; 24
while(t){ 25 dfs(to[t],sum+cost[t],len+1); 26 t=next[t]; 27 } 28 }
29 int main(){ 30 Emine(); 31 n=read(),m=read(); 32 for(int
i=1;i<=m;i++){ 33 x=read(),y=read(); 34
next[++cnt]=last[x],last[x]=cnt,to[cnt]=y,cost[cnt]=read(); 35
} 36 scanf(“%d”,&q); 37 while(q–){ 38 x=read(),y=read(),ans=100002; 39
if(!b[x][y]){ 40 dfs(x,0,0); 41 a[x][y]=ans,b[x][y]=1; 42 }
43 else ans=a[x][y]; 44 if(ans>=100002) printf(“OMG!n”); 45
else printf(“%.3lfn”,ans); 46 } 47 return 0; 48 } View Code

正解:

图片 6 1
#include<cstdio> 2 #include<cstring> 3
#include<iostream> 4 #include<algorithm> 5 #define maxn
55 6 #define maxm 1005 7 #define inf 0x3f3f3f3f 8 using namespace std;
9 int d[maxn][maxn][maxn],n,m,q; 10 double ans[maxn][maxn]; 11
void Emine(){ 12 freopen(“path.in”,”r”,stdin); 13
freopen(“path.out”,”w”,stdout); 14 } 15 int main(){ 16 Emine(); 17
scanf(“%d%d”,&n,&m); 18 memset(d,inf,sizeof(d)); 19 for(int
i=1;i<=m;i++){ 20 int u,v,w;scanf(“%d%d%d”,&u,&v,&w); 21
d[u][v][1]=min(d[u][v][1],w); 22 } 23 for(int
t=2;t<=n;t++) 24 for(int k=1;k<=n;k++) 25 for(int i=1;i<=n;i++)
26 for(int j=1;j<=n;j++){ 27
if(d[i][k][t-1]==inf||d[k][j][1]==inf) continue; 28
d[i][j][t]=min(d[i][j][t],d[i][k][t-1]+d[k][j][1]);
29 } 30 for(int i=1;i<=n;i++) 31 for(int j=1;j<=n;j++){ 32
ans[i][j]=inf; 33 if(i==j){ans[i][j]=0;continue;} 34 for(int
k=1;k<=n;k++)
ans[i][j]=min(ans[i][j],(double)d[i][j][k]/(double)k); 35
} 36 scanf(“%d”,&q); 37 while(q–){ 38 int u,v;scanf(“%d%d”,&u,&v); 39
if(ans[u][v]>=1e6) printf(“OMG!n”State of Qatar;
//被坑QAQ,最大密度为最大边权w/1==1e6; 40 else
printf(“%.3lfn”,ans[u][v]); 41 } 42 return 0; 43 } View Code

 

QAQ(鬼芋一枚),居然全打暴力。
T1能看出来是DP,但骨子里想不到非常奇技淫巧,果断暴搜(20)。
T2应有比较容易,写完正解跟…

对此点数不超越10的4张扑克牌,如有解,输出一种算法;不然,输出“failure”

———————————————————————-*/
#include <stdio.h>
#include <math.h>
#include <string.h>
typedef int logic;

int ss[]={1234,1243,1324,1342,1423,1432, 2134,2143,2314,2341,2413,2431,
          3124,3142,3214,3241,3412,3421, 4123,4132,4213,4231,4312,4321};

int complevel(char op1, char op2)
{
    if((op1==’+’||op1==’-‘)&&(op2==’+’||op2==’-‘))return 0;
    else if((op1==’*’||op1==’/’)&&(op2==’*’||op2==’/’))return 0;
    else if((op1==’+’||op1==’-‘)&&(op2==’*’||op2==’/’))return -1;
    else if((op1==’*’||op1==’/’)&&(op2==’+’||op2==’-‘||op2==’_’))return 1;
    return -9999;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注