3531. 定西

southern

开始时,将所有broken steps标记为0,为不可走
dp[0] = 1 // 标记起点,可走

状态转移方程:
if dp[i] == 0
dp[i] = 0 // this is broken step
else
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] // i - 3 >= 0

Wuxueqian

holy wow!i spent lots of time thinking how to DP.
thank you your idea!

Andrew-Malcom
[已删除]
wumiVon

//刚开始也是被用例4搞蒙了,才发现台阶n也能坏,相当于没有办法上去,答案为0

include

include

using namespace std;

int main()
{
int n, k;
scanf(“%d%d”, &n, &k);
vector v(n + 1);
for(int i = 0; i <= n; i++)
{
if(i == 0)
v[i] = 1;
else{
v[i] = 0;
}
}
for(int i = 0; i < k; i++)
{
int x;
scanf(“%d”, &x);
v[x] = -1;
}
for(int i = 1; i <= n; i++)
{
if(v[i] == -1) continue;
if(i - 1 >= 0 && v[i - 1] != -1)
{
v[i] += v[i - 1];
}
if(i - 2 >= 0 && v[i - 2] != -1)
{
v[i] += v[i - 2];
}
if(i - 3 >= 0 && v[i - 3] != -1)
{
v[i] += v[i - 3];
}
}
if(v[n] == -1) printf(“0”);
else{
printf(“%d”,v[n]);
}
return 0;
}

站在岸上的yu

int main()
{
int N, K;
cin >> N >> K;
bool damaged[110] = { 0 }; //记录损坏的台阶
int count[110] = { 0 }; //到达每个台阶的走法
int temp;

for (int i = 0; i < K; i++)
{
    scanf("%d", &temp);
    damaged[temp] = true;
}

count[0] = 1;   //从0开始走给0赋初值1
for (int i = 1; i <= N; i++)
{
    if (damaged[i] == false)    //如果楼梯没坏
    {
        if (i == 1)
        {
            count[i] += count[i - 1];
        }
        else if (i == 2)
        {
            count[i] += count[i - 1] + count[i - 2];
        }
        else
        {
            count[i] += count[i - 1] + count[i - 2] + count[i - 3];
        }
    }
}

printf("%d\n", count[N]);
return 0;

}

newCode

有哪位路过的大师提供一些思路

LzQuarter

case 4中存在输出为0的情况

lawson

也可递归判断。代码参考博客https://blog.csdn.net/liu16659/article/details/103823470

wjwjwj

状态转移方程 :dp[i] = dp[i + 1] + dp[i + 2] + dp[i + 3];

const int maxn = 105;
long long dp[maxn] = { 0 }, HashTable[maxn] = { 0 }; //HashTable记录台阶的好坏 0为好-1为坏,
int main() { //dp 记录当前台阶到最终台阶的步数
int n, k;
cin >> n >> k;
while (k–) {
int x;
cin >> x;
HashTable[x] = -1;
}
if (HashTable[n] == -1) {
cout << “0”;
return 0;
}
dp[n] = 1;
for (int i = n-1; i >= 0; i–) {
if (HashTable[i] == -1) {
dp[i] = 0; //坏台阶时候 dp为0
continue;
}
dp[i] = dp[i + 1] + dp[i + 2] + dp[i + 3];
}
cout<<dp[0];
return 0;
}

13627999316

直接搜索吧,水题可以不用dp

打死瓜皮

深度遍历算法

include

include

using namespace std;
int n,k,cnt=0;
set s;
void dfs(int x){
if(s.find(x)!=s.end()||x>n) return;
if(x==n){
cnt++;
return;
}
dfs(x+1);
dfs(x+2);
dfs(x+3);
}
using namespace std;
int main(){
scanf(“%d%d”,&n,&k);
for(int i=0;i<k;i++){
int tem;
scanf(“%d”,&tem);
s.insert(tem);
}
dfs(0);
printf(“%d”,cnt);
return 0;
}

改个名字吧

记得特判最后一级可能是坏的。。。。。。

xhliao

//AC代码

include

using namespace std;
int count=0;
int a[110];
int Isgood(int index,int k){
int i;
for(i=0; i>n>>k;
for(i=0; i>a[i];
}
Upst(0,k,n);
cout<<count<<endl;
return 0;
}

liuzb13

额,原来最后一阶如果是坏的就认为不能完成

lnu_cxn

谢了兄弟

10195101455

开始还以为是爬到最高一阶。。。结果看到case 4才知道这个点。

include

include

include

include

using namespace std;

struct Steps
{
int route;
bool broke;
};

int main()
{
struct Steps steps[101];
memset(steps, 0, sizeof(struct Steps)*101);
int N, K;
cin>>N>>K;
int k;
for(k = 0; k < K; k++)
{
int temp;
cin>>temp;
steps[temp].broke = true;
}
int n;
steps[0].route = 1;
for(n = 1; n <= N; n++)
{
if(steps[n-1].broke == false) steps[n].route += steps[n-1].route;
if(n >= 2&&steps[n-2].broke == false) steps[n].route += steps[n-2].route;
if(n >= 3&&steps[n-3].broke == false) steps[n].route += steps[n-3].route;
}
if(steps[N].broke == false) cout<<steps[N].route<<endl;
else cout<<0<<endl;
return 0;
}

YZAZJL

借鉴一楼大佬的
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
int i;
int a[n + 1];
// 将每个字节设置为1,此时每个int元素为16843009 = 0x1010101
memset(a,1,sizeof(a));
int tmp;
a[0]= 1;
for(i = 0; i < k; i++){
cin >> tmp;
a[tmp] = 0;
}
for(i = 1; i < n + 1; i++){
if(a[i] == 0){
a[i] = 0;
}else{
if(i == 1){
a[i] = a[i -1];
}else if(i == 2){
a[i] = a[i - 1] + a[i - 2];
}else{
a[i] = a[i - 1] + a[i - 2] + a[i - 3];
}
}
}
cout << a[n] << endl;
return 0;
}

你当前正在回复 博客/题目
存在问题!