月度归档：2017年07月

洛谷 金明的预算方案

发表评论

题号：P1064
一维滚动数组优化。

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,m;
int v[65],p[65],q[65],w[65];
int q1[65],q2[65];
int iptr;
int f[35000];
void insert_subgood(int main,int sub){
    if(q1[main]==0)q1[main]=sub;
    else q2[main]=sub;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>v[i]>>p[i]>>q[i];
        w[i]=v[i]*p[i];
        if(q[i]!=0){
            insert_subgood(q[i],i);
        }
    }
    for(int i=1;i<=m;i++){
        if(q[i]!=0)continue;
        for(int j=n;j>=0;j--){
            if(j-v[i]>=0)
                f[j]=max(f[j],f[j-v[i]]+w[i]);
            if(q1[i]!=0&&j-v[i]-v[q1[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q1[i]]]+w[i]+w[q1[i]]);
            if(q2[i]!=0&&j-v[i]-v[q2[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q2[i]]]+w[i]+w[q2[i]]);
            if(q1[i]!=0&&q2[i]!=0&&j-v[i]-v[q1[i]]-v[q2[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q1[i]]-v[q2[i]]]+w[i]+w[q1[i]]+w[q2[i]]);
        }
    }
    cout<<f[n];
}

洛谷 八皇后

发表评论

题号1219

感觉写的非常满意……哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
n=13都不用打表啦！

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n;
int cnt;//情况计数器
bool line[14],row[14],left_diagonal[26],right_diagonal[26];
//占用情况数组：行；列；左上-右下对角线；右上-左下对角线
int pos[14];
//记录每一行的棋子放在哪一列
inline int calculate_left_dia(int x,int y){//计算x行y列的棋子在第几个左上-右下对角线上
    return x+y-1;
}
inline int calculate_right_dia(int x,int y){//计算x行y列的棋子在第几个右上-左下对角线上
    return (n+1-x)+y-1;
}
void search(int level){//dfs搜索：行
    if(level==n+1){//递归基
        cnt++;
        if(cnt>3)return;
        for(int i=1;i<=n;i++){//输出结果
            cout<<pos[i]<<" ";
        }
        cout<<endl;
    }
    for(int i=1;i<=n;i++){//遍历列
        if(!line[i]&&!row[i]&&!left_diagonal[calculate_left_dia(level,i)]&&!right_diagonal[calculate_right_dia(level,i)]){//满足要求
            pos[level]=i;
            line[i]=true;row[i]=true;
            left_diagonal[calculate_left_dia(level,i)]=true;
            right_diagonal[calculate_right_dia(level,i)]=true;
            search(level+1);//继续深搜
            line[i]=false;row[i]=false;//回溯
            left_diagonal[calculate_left_dia(level,i)]=false;
            right_diagonal[calculate_right_dia(level,i)]=false;
        }
    }
}
int main(){
    cin>>n;
    search(1);
    cout<<cnt;
}

洛谷 滑雪（重要！）

发表评论

题号:P1434
这道题需要留着细细品味……
这道题也挺恶心，用尽各种优化方法……
需要写一下注释，省得我以后看不懂自己写的代码……

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int array[105][105];
int memory[105][105];
bool check[105][105];
struct s{
    int x,y,n;
    bool operator < (s& s2){
        return this->n>s2.n;
    }
}ss[11025];
int r,c;
int shift_x[5]={0,-1,1,0,0},shift_y[5]={0,0,0,-1,1};//left,right,up,down
int safe_array(int x,int y){
    if(x>=1&&x<=r&&y>=1&&y<=c)return array[x][y];
    else return -1;
}//保证数组不越界
int dfs(int x,int y,int last){//dfs是从截止点step为0推到起始点的
    if(safe_array(x,y)==-1||last<=array[x][y]||check[x][y])return 0;
    if(memory[x][y]!=-1)return memory[x][y];
    check[x][y]=true;
    int max_=-1;
    for(int i=1;i<=4;i++){
        int t=dfs(x+shift_x[i],y+shift_y[i],array[x][y]);
        if(t>max_)max_=t;
    }
    check[x][y]=false;
    return memory[x][y]=max_+1;
}
int main(){
    memset(memory,-1,sizeof(memory));
    cin>>r>>c;
    int ptr=0;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>array[i][j];
            ss[ptr].x=i;
            ss[ptr].y=j;
            ss[ptr].n=array[i][j];
            ptr++;
        }
    }
    int max_=-1;
    sort(ss,ss+ptr);//先排序，由坡高到坡低去进行dfs，这样坡低的在刚一开始就会因为记忆化搜索直接return
    for(int i=0;i<ptr;i++){
        int t=dfs(ss[i].x,ss[i].y,ss[i].n+1);
        if(t>max_)max_=t;//收集最长路径
    }
    cout<<max_;
}

20180730更新：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<functional>
using namespace std;
int r,c;
int arr[105][105];
int f[105][105];
struct node{
    int x,y;
    int v;
    bool operator < (const node& n2){
        return v<n2.v;
    }
}narr[10005];
int narrptr=0;
int main() {
    ios::sync_with_stdio(false);
    memset(arr,0x7f,sizeof(arr));
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>arr[i][j];
            narr[++narrptr].v=arr[i][j];
            narr[narrptr].x=i;
            narr[narrptr].y=j;
        }
    }
    sort(narr+1,narr+r*c+1);
    for(int i=1;i<=narrptr;i++){
        if(narr[i].v>arr[narr[i].x-1][narr[i].y])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x-1][narr[i].y]+1);
        if(narr[i].v>arr[narr[i].x+1][narr[i].y])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x+1][narr[i].y]+1);
        if(narr[i].v>arr[narr[i].x][narr[i].y-1])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x][narr[i].y-1]+1);
        if(narr[i].v>arr[narr[i].x][narr[i].y+1])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x][narr[i].y+1]+1);
    }
    int mmax=0;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            mmax=max(mmax,f[i][j]);
        }
    }
    cout<<mmax+1;
}

洛谷 [USACO06FEB]数字三角形Backward Digit Su…

发表评论

题号：P1118

必须用杨辉三角/组合数的方法做，同时要剪枝……这样才能A。不用这个只能60，剩下的全部TLE。

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int n,sum;
bool check[13];
int current[13];
int current_temp[13];
int yanghui[13];
int calculate(int k){
    int sum=0;
    for(int i=0;i<k;i++){
        sum+=yanghui[i]*current[i];
    }
    return sum;
}
void search(int level){
    if(level==n&&calculate(n)==sum){
        for(int i=0;i<n;i++){
            cout<<current[i]<<" ";
        }
        exit(0);
    }
    for(int i=1;i<=n;i++){
        if(!check[i]){
            check[i]=true;
            current[level]=i;
            if(calculate(level)<sum)search(level+1);
            check[i]=false;
        }
    }
}
int main(){
    memset(check,false,sizeof(check));
    cin>>n>>sum;
    //calculate yanghui
    yanghui[0]=1;
    for(int i=1;i<n;i++){
        yanghui[i]=(n-i)*yanghui[i-1]/i;
    }
    //end calculate
    search(0);
}

20180730更新：都忘了杨辉三角了……

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
#include<iostream>
using namespace std;
int n,sum;
bool visited[15];
int ansarr[15];
int triangle[15][15];
void triangle_init(){
    for(int i=0;i<15;i++){
        triangle[i][0]=1;
        triangle[i][i]=1;  
    }
    for(int i=2;i<15;i++){
        for(int j=1;j<i;j++){
            triangle[i][j]=triangle[i-1][j]+triangle[i-1][j-1];
        }
    }
}
bool dfs(int pos,int s){
    if(pos==n+1)return s==sum;
    if(s>sum)return false;
    for(int i=1;i<=n;i++){
        if(visited[i])continue;
        visited[i]=true;
        ansarr[pos]=i;
        if(dfs(pos+1,s+i*triangle[n-1][pos-1]))return true;
        visited[i]=false;
    }
    return false;
}
int main() {
    triangle_init();
    cin>>n>>sum;
    if(dfs(1,0))for(int i=1;i<=n;i++)cout<<ansarr[i]<<" ";
}

洛谷 拼数

发表评论

题号：1012

这题也挺逗的，没有想到能这么做……
看了别人的题解……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
bool cmp(string & s1,string & s2){
    return s1+s2>s2+s1;
}
int main(){
    int n;
    cin>>n;
    string s[20];
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    sort(s,s+n,cmp);
    for(int i=0;i<n;i++){
        cout<<s[i];
    }
}

洛谷 均分纸牌

发表评论

题号：1031

参考某大神的题解，受了点启发，想了个思路，有可能是和别人是重的，但我还是说一下，毕竟别人的不是特别好懂。

首先读入数据，计算出每个堆上应有的平均分配之后的值。既然最终的目的是要求所有堆都统一为平均值，那我就先不管后面的，先把现在的当前堆管好再说。利用贪心的想法，从左向右遍历，当前堆上的牌数小于平均值就从右面一个堆往过要，大于平均值就把多的全部扔给右面一个堆。过程中有可能出现负数，但是最后肯定是会回到正常的状态。每个堆上的牌至多主动挪出一次，是符合题目要求的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int main(){
    int n,arr[101],sum=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        sum+=arr[i];
    }
    int avg=sum/n;
    int step=0;
    for(int i=1;i<n;i++){
        if(arr[i]<avg){
            step++;
            arr[i+1]-=avg-arr[i];
        }else if(arr[i]>avg){
            step++;
            arr[i+1]+=arr[i]-avg;
        }
    }
    cout<<step;
}