日度归档：16 7 月, 2017

洛谷 滑雪（重要！）

发表评论

题号: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];
    }
}