$$Cat$$ 喜欢跳舞的线的音乐，于是就有了这一道题，给你一个 $$h times w$$ 的方格棋盘，棋盘上有一颗棋子最开始在左上角 $$$$，棋子只能往右走或者往下走，棋子最后要走到右下角 $$$$. 在棋子走的过程中，如果当前走的方向与上一次走的方向不同，则称棋子拐了一下弯，例如下图，棋子在行进过程中拐了三次，也就是有三个拐点，现在 $$Cat$$ 想要知道拐点为 $$k$$ 的时候有多少种走法，对于 100% 的数据 $$2 le h, w le 15, quad 1 le k le h + w - 3$$
$$Cat$$ 喜欢跳舞的线的音乐，于是就有了这一道题。 给你一个 $$h times w$$ 的方格棋盘，棋盘上有一颗棋子最开始在左上角 $$(1, 1)$$，棋子只能往右走或者往下走，棋子最后要走到右下角 $$(w, h)$$  在棋子走的过程中，如果当前走的方向与上一次走的方向不同，则称棋子拐了一下弯。 例如下图，棋子在行进过程中拐了三次，也就是有三个拐点。  现在 $$Cat$$ 想要知道拐点为 $$k$$ 的时候有多少种走法。 第一行有三个整数 $$h, w, k$$（$$h$$ 行，$$w$$ 列，$$k$$ 个拐点） 输出在拐点个数为 $$k$$ 时有多少种走法。 3 3 2 2 对于 80% 的数据 $$2 le h, w le 7, quad 1 le k le h + w - 3$$ 对于 100% 的数据 $$2 le h, w le 15, quad 1 le k le h + w - 3$$ 这道题其实放了很多水，暴力可得80分。 ## 出题者
CatCatCat 喜欢跳舞的线的音乐，于是就有了这一道题。 给你一个 h×wh times wh×w 的方格棋盘，棋盘上有一颗棋子最开始在左上角 (1,1)(1, 1)(1,1)，棋子只能往右走或者往下走，棋子最后要走到右下角 (w,h)(w, h)(w,h) 在棋子走的过程中，如果当前走的方向与上一次走的方向不同，则称棋子拐了一下弯。 例如下图，棋子在行进过程中拐了三次，也就是有三个拐点。 现在 CatCatCat 想要知道拐点为 kkk 的时候有多少种走法。 .katex { font-size: 1.4em!important; } @font-face { font-family: 'KaTeX_AMS'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_AMS-Regular.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_AMS-Regular.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_AMS-Regular.ttf) format('truetype'); font-weight: normal; font-style: normal; } @font-face { font-family: 'KaTeX_Caligraphic'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Caligraphic-Bold.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Caligraphic-Bold.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Caligraphic-Bold.ttf) format('truetype'); font-weight: bold; font-style: normal; } @font-face { font-family: 'KaTeX_Caligraphic'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Caligraphic-Regular.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Caligraphic-Regular.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Caligraphic-Regular.ttf) format('truetype'); font-weight: normal; font-style: normal; } @font-face { font-family: 'KaTeX_Fraktur'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Fraktur-Bold.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Fraktur-Bold.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Fraktur-Bold.ttf) format('truetype'); font-weight: bold; font-style: normal; } @font-face { font-family: 'KaTeX_Fraktur'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Fraktur-Regular.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Fraktur-Regular.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Fraktur-Regular.ttf) format('truetype'); font-weight: normal; font-style: normal; } @font-face { font-family: 'KaTeX_Main'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Main-Bold.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Main-Bold.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Main-Bold.ttf) format('truetype'); font-weight: bold; font-style: normal; } @font-face { font-family: 'KaTeX_Main'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Main-BoldItalic.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Main-BoldItalic.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Main-BoldItalic.ttf) format('truetype'); font-weight: bold; font-style: italic; } @font-face { font-family: 'KaTeX_Main'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Main-Italic.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Main-Italic.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Main-Italic.ttf) format('truetype'); font-weight: normal; font-style: italic; } @font-face { font-family: 'KaTeX_Main'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Main-Regular.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Main-Regular.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Main-Regular.ttf) format('truetype'); font-weight: normal; font-style: normal; } @font-face { font-family: 'KaTeX_Math'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Math-BoldItalic.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Math-BoldItalic.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Math-BoldItalic.ttf) format('truetype'); font-weight: bold; font-style: italic; } @font-face { font-family: 'KaTeX_Math'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Math-Italic.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Math-Italic.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Math-Italic.ttf) format('truetype'); font-weight: normal; font-style: italic; } @font-face { font-family: 'KaTeX_SansSerif'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_SansSerif-Bold.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_SansSerif-Bold.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_SansSerif-Bold.ttf) format('truetype'); font-weight: bold; font-style: normal; } @font-face { font-family: 'KaTeX_SansSerif'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_SansSerif-Italic.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_SansSerif-Italic.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_SansSerif-Italic.ttf) format('truetype'); font-weight: normal; font-style: italic; } @font-face { font-family: 'KaTeX_SansSerif'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_SansSerif-Regular.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_SansSerif-Regular.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_SansSerif-Regular.ttf) format('truetype'); font-weight: normal; font-style: normal; } @font-face { font-family: 'KaTeX_Script'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Script-Regular.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Script-Regular.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Script-Regular.ttf) format('truetype'); font-weight: normal; font-style: normal; } @font-face { font-family: 'KaTeX_Size1'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Size1-Regular.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Size1-Regular.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Size1-Regular.ttf) format('truetype'); font-weight: normal; font-style: normal; } @font-face { font-family: 'KaTeX_Size2'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Size2-Regular.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Size2-Regular.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Size2-Regular.ttf) format('truetype'); font-weight: normal; font-style: normal; } @font-face { font-family: 'KaTeX_Size3'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Size3-Regular.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Size3-Regular.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Size3-Regular.ttf) format('truetype'); font-weight: normal; font-style: normal; } @font-face { font-family: 'KaTeX_Size4'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Size4-Regular.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Size4-Regular.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Size4-Regular.ttf) format('truetype'); font-weight: normal; font-style: normal; } @font-face { font-family: 'KaTeX_Typewriter'; src: url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Typewriter-Regular.woff2) format('woff2'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Typewriter-Regular.woff) format('woff'), url(https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/fonts/KaTeX_Typewriter-Regular.ttf) format('truetype'); font-weight: normal; font-style: normal; } var box = new Array(); $(function() { var _list = document.getElementsByClassName("panel_prob_body") for (i = 1; i <= 5; ++i) { _list[i].id = "box" + i; if (i == 3 || i == 4) { _list[i].innerHTML = "
" + $("#text" + i).text() + ""
} else {
_list[i].innerHTML = ""
}
}
for (i = 0; i <= 5; ++i) {
// alert(i);
if (i == 3 || i == 4) {
continue;
} else {
box[i] = editormd.markdownToHTML("box" + i, {
markdown : $("#text" + i).text(),
htmlDecode : "style,script,iframe", // you can filter tags decode
tocm : true,
emoji : true,
taskList : true,
tex : true, // 默认不解析
flowChart : true, // 默认不解析
sequenceDiagram : true, // 默认不解析
});
}
}
// document.body.scrollTop = 0;
// document.documentElement.scrollTop = 0;
});
想要在职场中立于不败之地？那就来试试全网最全C++题库，让您在练习中快速提升技能。
标签： 编程练习 基础2556: 跳舞的线题解
